Távolság grafikonok
Legyen G =
Legrövidebb (Vi, Vj) -marshruta nevezett közötti távolság a csúcsok vi és vj, jelöljük # 63; (Vi, Vj).
tesz # 63; (Vi, Vj) = 0. Nyilvánvaló, hogy az így bevezetett távolság mértéket kielégíti a következő axiómák:
1) # 63; (Vi, Vj) # 63; 0;
2) # 63; (Vi, Vj) = 0 # 45; Vi = Vj
3) # 63; (Vi, Vj) = # 63; (Vi, Vj) - szimmetria
4) # 63; (Vi, Vj) # 63; # 63; (Vi, Vj) + # 63; (Vj, Vk) - a háromszög-egyenlőtlenség.
Ha V =, akkor a mátrix P = (pi, j) = # 63; (Vi, Vj), az úgynevezett mátrix távolságok (ahol a P mátrix szimmetrikus).
Rögzített vertex V érték E (V) = max <? (Vi, Vj) | Vj є V> az úgynevezett excentricitása a vertex V. Így a excentricitása a vertex egyenlő a távolság e csúcsból a legtávolabbi azokból.
Ha a P-távolság mátrix, a E excentricitásának (Vi) egyenlő a legnagyobb számú, álló, i-edik sorának.
A maximális excentricitása minden a gráf G említett átmérő d jelöli (G). d (G) = vf [. A tetején a V az úgynevezett perifériális, ha E (v) = d (G).
Vegyünk egy példát. Azt találjuk, az átmérője a G gráf, a 18. ábra. távolságok R mátrix formájában:
Ennélfogva, E (1) = 3, E (2) = 2, és E (3) = 3, és E (4) = 2 e (5) = 2, és ezért, d (G) = 3. A csúcsok 1 és 3 Ezek periféria.
Minimális excentricitása a G gráf azt mondta, hogy annak sugara, jelölje r (G). R (G) = min.
Ez az úgynevezett központi vertex V, ha E (V) = R (G).
A készlet minden központi gráf pontjai az úgynevezett közepén.
Tekintsük a következő példát. A sugara a grafikon a 18. ábrán látható, értéke 2, és a középpontja van beállítva.
A probléma megtalálni a központi csúcsok a gyakorlati tevékenység. Tegyük fel például, a grafikon egy úthálózat, azaz Emberi csúcsok megfelelnek a pontokat, és az élek - utak között. Ez történik optimálisan kórházak, benzinkutak, stb Ilyen helyzetekben az optimalizálás az, hogy minimalizáljuk a távolság a szolgálati helyen, hogy a legtávolabbi szélén. Következésképpen elhelyezések központi szerepet kell betöltenie csúcs. Valós problémák eltérnek az ideális téma, hogy van, hogy figyelembe kell venni egyéb körülmények - a távolság a települések közötti, a költségek, az utazási idő, stb
Fa - az egyik leggyakoribb fogalmak elméletileg grafikonokat (19. ábra).
Egyértelmű, hogy a „különleges helyet” a fa foglalják nemcsak a felső lóg. Állnak ki a fák tetejére, és amelyet egy dupla kört. Az ilyen csúcsok nevezzük gyökér.
A gyökér csomópont nem nehéz megkülönböztetni a fák ábrákon 20, 21, 22.
Az első esetben, a gyökér csomópont az egyetlen csúcsa A, a második - a C csúcsból a harmadik (a fa, minden csúcs egy kivételével, lóg, az úgynevezett „csillag”) - a felső A. De mi tekinthető a tetején a gyökér az oszlopokban, amely ábrákon mutatjuk be a 23., 24. és 25.?
Ez természetes, hogy azt feltételezik, hogy mind a három fák két gyökércsúcs. A fa 23. ábra - az A és B a fa 24. ábra - a C és D, a fa 25. ábra - A és B.
A d távolság (Vi, Vj) között a csúcsok vi és vj G gráfot nevezzük a hossza a legrövidebb utat összekötő őket. (Ha a gráf G-fát, az utat csúcsokat összekötő vi és vj, csak).
Kiszámítjuk az egyes csúcsa a fa a 26. ábrán látható, a legnagyobb a távolság az összes többi csúcsot, és írd fel ezeket a számokat az ábrán közel a csúcs (27. ábra).
Ezek közül a legnagyobb számban hívják az átmérője a grafikon (ebben az esetben egy fa), a legkisebb - Count sugara.
A fa tetején, ahol a maximális távolságok más csúcsai azonos sugarú, az úgynevezett gyökér. A fa a 26. ábrán látható, az átmérő 5, és a sugár értéke 3; gyökércsúcs - A és B.
Feladat. Számítsuk ki a átmérője és sugara a grafikon alább látható:
Mi megoldjuk egy másik probléma a kémia, „telített szénhidrogén-vegyület az úgynevezett szén-C, és amelynek vegyértéke 4 N hidrogén-vegyértékű 1, ahol ha a megadott számú szénatomot tartalmaz a legnagyobb számú hidrogénatomok. Formula kap telített szénhidrogén n szénatomos ".
Tekintsünk egy gráf, amelynek csúcsai atomok és a bordák - a vonatkozó közötti kovalens kötések őket. Mutassuk meg, hogy éppen ellenkezőleg, hogy nincs ciklus a grafikonon, azaz Talán bekapcsolása a felső szélei a grafikon felső, visszatér a kiindulási csúcsból. Ha a ciklus, meg kell szénatomokból felépülő, mivel a hidrogén van egy vegyértéke, 1 és lehet csatlakoztatni csak egy atom. Ez a ciklus létezése szakadás kötést két szénatom között, és kapcsolódik mindegyik még egy hidrogénatom. A hidrogénatomok számát növeli, majd az eredeti gráf leíró nem telített szénhidrogén-molekula.
A bordák mehet az épület egy gráf minden csomópont minden más, és nincsenek ciklusok. Egy ilyen görbét nevezzük fa. Legyen molekula, amely tartalmazza n szénatomot tartalmazó alkilcsoport és m hidrogénatom, akkor a grafikon fog tartalmazni n + m csúcsok. Továbbá, a probléma megoldásának a könnyen bizonyítható használat aránya: élek száma a fa eggyel kevesebb, mint a csúcsok száma. Következésképpen, az oszlop n + m - 1 éle. A gráf csúcsok jelölik a szénatomok ki a 4 bordák és a csúcsok jelentése hidrogénatom, - az egyik. A puszta tény, hogy az összeg a vertex fok, azaz számának összege a bordák, lehetőség van, hogy írjon a kapcsolatban: 4n + m = 2 (n + m - 1). Ebből következik, hogy m = 2n + 2, ezért a képlet egy telített szénhidrogén n szénatomos: CnH2n + n.
Ie általános képletű vegyület alkalmazásával állíthatjuk elő a matematika, kizárólag a meghatározására és a teljesítő kémiai kísérletek.
Számának korlátozásával a (nem-ciklus) utal szénhidrogének, így pentán S5N12. A szerkezeti képlet mutatja a 28. ábra Ez a képlet tudunk egy-az-egyhez megfelelés egyetlen gyökeres fának (ábra. 29), amely bemutatja a kölcsönös elrendezése csupán szénatomot a molekulában pentán. De így egyértelműen meghatározható, és a helyét a hidrogénatomok a molekula. A 30. ábra a szerkezeti képlete egy molekula isopentanes, és a 31. ábra megfelelő ez dvukornevoe fa.
Az egyik vagy másik ok miatt, szinte minden munkát gráfelméleti tele a magok a lehetséges gyakorlati alkalmazások, vagy legalábbis potenciálisan hasznos.
A grafikonok hatékonyan használják a tervezési és menedzsment elmélet, ütemezés elmélet, a szociológia, a közgazdaságtan, a biológia, az orvostudomány, az alábbi területeken alkalmazott matematika.