A gráfelmélet alkalmazásai
Sík grafikonok
A G gráfot síknak tekintik, ha egy síkon ábrázolható úgy, hogy a csúcsok mind különálló pontok, az élek egyszerű görbék, és két szélük nem találkozik egymással, kivéve a végükön. Például, a K 4, a négy csúcs teljes gráfja sík, ahogy a 4A. Ábra is mutatja.
Két gráfot homeomorfnak tekintik, ha mindkettőt ugyanabból a gráfból lehet nyerni élek felosztásával. Például a 4A. És 4B. Ábra grafikonjai homeomorfak.
A K m, n gráf egy olyan gráf, amelynél a csúcskészlet két részhalmazra osztható: az egyik m csúcsú, a másik n csúcs. Ugyanazon részhalmaz bármelyik csúcsa nem szomszédos, míg a különböző részhalmazok bármelyik csúcsa szomszédos. A lengyel matematikus, Kazimierz Kuratowski 1930-ban a következő híres tételt bizonyította:
A G gráf síkjának szükséges és elegendő feltétele, hogy az ne tartalmazzon az 5. ábrán bemutatott K 5 vagy K 3,3-ra vonatkozó homeomorf alrajzot.
Az elemi összehúzódása G gráf egy átalakítása G egy új gráf G 1, oly módon, hogy két szomszédos csúcs u és υ G helyébe egy új csúcs w G 1 és w szomszédos G 1, hogy az összes csúcsot, hogy A G * gráfról azt mondják, hogy G összehúzódása, ha G * G-ből származtatható elemi összehúzódások sorozatával. Az alábbiakban egy síkbeli grafikon egy további jellemzését mutatjuk be a német matematikus K. Wagner 1937-ben.
A gráf sík akkor és csak akkor, ha nem összehúzódó K 5 vagy K 3,3 értékkel.
A négyszínű térkép probléma
A négyszínű térkép probléma megoldása több mint egy évszázada elkerülte minden elemzőt, aki megpróbálta. Lehetséges, hogy a probléma felhívta Möbius figyelmét, de úgy tűnik, hogy az első írásbeli utalás egy Francis Guthrie testvérének, az Augustus De Morgan diákjának 1852-ben küldött levele.
A probléma a síkbeli térképeket érinti, vagyis a sík nem átfedő régiókra történő felosztását egyszerű zárt görbékkel határolva. A földrajzi térképekben empirikusan megfigyelték, hogy sok különleges esetben megpróbálták: legfeljebb négy színre van szükség a régiók színezésére, hogy két közös határral rendelkező két régió mindig eltérő színű legyen, és bizonyos esetekben legalább négy színre van szükség. (Azon régiók, amelyek csak egy ponton találkoznak, például Colorado állam és Arizona állam az Egyesült Államokban, nem tekinthetők közös határnak). Ennek az empirikus megfigyelésnek a formalizálása képezi az úgynevezett „négyszínű tétel” elnevezést. A probléma az állítás bizonyítása vagy megcáfolása, hogy ez a helyzet minden síkbeli térkép esetében. Ez a három szín nem elegendő könnyen bizonyítható, míg öt szín megfelelőségét 1890-ben a brit matematikus PJ Heawood bizonyította.
1879-ben az AB Kempe angol angol megoldást javasolt a négyszínű problémára. Noha Heawood rámutatott arra, hogy Kempe érvelése hibás, két fogalma eredményesnek bizonyult a későbbi vizsgálatok során. Ezek közül az egyik, az elkerülhetetlenségnek nevezett, helyesen kijelenti, hogy nem lehet olyan térképet elkészíteni, amelyben négy konfiguráció sem létezik (ezek a konfigurációk két szomszédos régióból állnak, egyet háromból, egyet négyből és egyet ötből). A második fogalom, a redukálhatóság fogalma Kempe érvényes bizonyítékából származik, amely szerint ha létezik olyan térkép, amely legalább öt színt igényel, és amely négy (vagy három vagy kettő) szomszédságú régiót tartalmaz, akkor legyen öt színek kisebb számú régióban. Kempe tévesen próbálta bizonyítani egy öt szomszéddal rendelkező régiót tartalmazó térkép reducibilitását, ám ezt helyesbítették egy 1976-ban Kenneth Appel és Wolfgang Haken, az Egyesült Államok által közzétett bizonyítékban. Bizonyításuk némi kritikát váltott ki, mivel 1936 különálló eset értékelését tette szükségessé, amelyek mindegyike 500 000 logikai műveletet tartalmazott. Appel, Haken és munkatársaik olyan programokat dolgoztak ki, amelyek lehetővé tették egy nagy digitális számítógép számára, hogy ezeket az adatokat kezelje. A számítógép több mint 1000 órát igényelt a feladat végrehajtásához, és az ebből származó formális bizonyíték több száz oldal hosszú.
Eulerian ciklusok és a Königsberg-híd problémája
A G multigráf a csúcsok nem üres V (G) halmazából és az V (G) különálló elemének rendezetlen párok halmazának E (G) részhalmazából áll, amelyek f-értéke ≥ 1 az egyes párokhoz. Ha az f frekvenciájú (x 1, x 2) páros E (G) -hez tartozik, akkor az x 1 és x 2 csúcsokat f élek kötik össze.
A multigráfiai elem Eulerian ciklusa egy zárt lánc, amelyben minden él pontosan egyszer jelenik meg. Euler megmutatta, hogy a multigráf akkor és csak akkor rendelkezik egy Euler-ciklussal, ha össze van kapcsolva (az elkülönített pontokon kívül), és a páratlan fokú csúcsok száma nulla vagy kettő.
Ez a probléma először a következő módon merült fel. A Pregel-folyó, melyet két ága összefolyása képez, Königsberg városán áthalad és a Kneiphof-sziget mindkét oldalán folyik. Hét híd volt, ahogy a 6A. Ábra mutatja. A városlakók elgondolkodtak azon, hogy lehet sétálni, és csak egyszer és egyszer áthidalni az egyes hidakat. Ez megegyezik egy Euler-ciklus megtalálásával a 6B. Euler lehetetlennek bizonyította, mert négy páratlan rendű csúcs van.
