Teyori graf

teyori graf - li se youn nan alineya yo nan matematik, karakteristik prensipal la nan ki se metòd la jewometrik nan etid la nan objè yo. Li se te konsidere kòm fondatè a matematisyen nan pi popilè Euler.

Aplikasyon an nan teyori graf nan fen 19yèm syèk la, yo te redwi a solisyon an nan pwoblèm ki enteresan epi atire konsiderab atansyon piblik la. Apati de 20yèm syèk la, lè yo te teyori a graf fòme kòm yon disiplin endepandan matematik, li te lajman ki itilize nan domèn tankou sibèrnetik, fizik, lojistik, pwogramasyon, byoloji, elektwonik, transpò ak sistèm kominikasyon.

konsèp debaz nan teyori graf

baz la se yon graf. ka tèminoloji a ka jwenn tankou yon bagay tankou yon rezo ki idantik ak kolòn nan. Denye - se nimewo ki pa vid nan pwen, se sa ki, somè ak segments, sa vle di zo kòt yo, tou de bout nan ki koresponn ak yon chif yo bay nan pwen. teyori graf pa envesti yon pwen sèten nan valè yo nan bor ak somè. Pou egzanp, wout vil la ak konekte yo, kote premye a - somè yo nan graf la, ak dezyèm - kòt la. se pi gwo enpòtans bay teyori a nan ark yo. Si bor yo gen yon direksyon, yo rele sa arc ak la, si yon graf ki gen pwent dirije, yo rele sa yon digrafi.

Nan tèminoloji a nan teyori a menm jan se konsèp sa yo:

Subgraph se graf la, tout bor ak somè se yo ki pami somè yo ak bor.

Konekte graf - yon sèl ki gen de tèt diferan egziste chèn konekte yo.

Pondere konekte graf - yon sèl ki mete fonksyon an pondération.

Tree - konekte graf san yo pa sik.

Skelèt - yon subgraph ki se yon pye bwa.

Nan imaj la graf nan plan defini notasyon a se te itilize: pwen an somè chwazi koresponn ak sifas la lekòl primè ak si kwen an se ant somè, pwen yo respektif yo konbine segman. Si graf la-oryante, segments sa yo yo ranplase pa flèch yo.

Men, pa konpare imaj la graf avè l ', sa vle di ak yon estrikti abstrè, paske ka yon sèl graf ap bay plis pase yon reprezantasyon grafik. Desen sou plan an yo bay yo nan lòd yo wè ki pè somè ini bor, epi ki yo pa.

Pami kèk nan travay yo nan teyori graf distenge:

1. Pwoblèm lan nan kous la pi kout (ranplasman pyès ki nan konpitè, plasman, anbilans ak echanj telefòn).
2. Maksimòm pwoblèm koule (mouvman kòmann-nan nan yon rezo dinamik, distribisyon nan travay, òganizasyon an nan kapasite).
3. Pwoblèm lan nan penti yo ak pakè (sant aranjman telegram).
4. Koloran nan kolòn (plasman memwa sou òdinatè elektwonik).
5. rezo kominikasyon ak graf (kreye yon rezo kominikasyon, analiz la nan rezo kominikasyon).

Nan moman sa a prezan li enposib nan pwogram majorite nan travay san yo pa konnen an nan teyori graf. Sa fè li pi fasil ak pi fasil yo travay avèk òdinatè.

Pwogram sèvi ak yon varyete de estrikti ak metòd inivèsèl pou rezoud pwoblèm, ak youn nan yo, se teyori a nan graf. ka enpòtans li diman dwe surèstimasyon. teyori graf nan pwogram fè li posib yo senplifye rechèch la pou enfòmasyon, yo optimize lojisyèl an, konvèti epi distribye done. Atravè algoritm teyori rive posibilite pou sèvi ak yo nan evalyasyon pou travay espesifik pote soti nan modifikasyon an nan algorithm nan, san yo pa diminye degre nan fyab nan matematik vèsyon fini nan pwogram lan.

Yon pwopriyete enpòtan nan sistèm kontwòl la oswa modèl se yon seri relasyon binè ak mete nan nan aksyon ak inite done. Sa yo estrikti se yon pati nan sèlman nan pwogram nan epi li se enfòmasyon ki transfòme pa yo. Se poutèt sa, graf yo ki baze sou desen an pou pwogramè a.