Grafų teorijos taikymai
Plokštieji grafikai
Sakoma, kad grafikas G yra plokščias, jei jį galima pavaizduoti plokštumoje tokiu būdu, kad visos viršūnės yra atskiri taškai, kraštai yra paprastos kreivės ir nė vienas kraštas nesutampa vienas su kitu, išskyrus jų gnybtus. Pavyzdžiui, K 4, visas keturių viršūnių grafikas, yra plokščias, kaip parodyta 4A paveiksle.
Manoma, kad du grafikai yra homeomorfiniai, jei abu galima gauti iš to paties grafiko, padalijant kraštus. Pavyzdžiui, 4A ir 4B paveikslų grafikai yra homeomorfiniai.
K m, n grafikas yra grafikas, kurio viršūnių aibę galima padalyti į du pogrupius: vieną su m viršūnėmis, kitą su n viršūnėmis. Bet kurios dvi to paties pogrupio viršūnės nėra gretimos, tuo tarpu bet kurios dvi skirtingų pogrupių viršūnės yra gretimos. Lenkų matematikas Kazimieras Kuratowskis 1930 m. Įrodė šią garsiąją teoremą:
Būtina ir pakankama sąlyga, kad G grafikas būtų plokščias, yra tai, kad jame nėra 5 paveiksle parodyto K 5 arba K 3,3 homeomorfinio pogrupio.
Elementarus grafiko G susitraukimas yra G transformacija į naują grafą G 1 taip, kad dvi gretimos G viršūnės u ir υ G 1 pakeičiamos nauja viršūne w G 1, o w yra G 1 greta visų viršūnių iki kurios u arba υ yra gretimos G. Grafikas G * yra tariamas kaip G susitraukimas, jei G * galima gauti iš G elementarių susitraukimų seka. Toliau pateiktas dar vienas plokščiojo grafiko apibūdinimas dėl vokiečių matematiko K. Wagnerio 1937 m.
Grafikas yra plokščias tada ir tik tada, kai jis negali būti susitraukiantis su K 5 ar K 3,3.
Keturių spalvų žemėlapio problema
Daugiau nei šimtmetį keturių spalvų žemėlapio problemos sprendimas išspręstas kiekvienam bandžiusiam analitikui. Ši problema galbūt patraukė Möbius dėmesį, tačiau atrodo, kad pirmoji rašytinė nuoroda į ją yra vieno Pranciškaus Guthrie laiškas savo broliui, Augusto De Morgano studentui, 1852 m.
Problema susijusi su plokštuminiais žemėlapiais, ty plokštumos padalijimu į nepersidengiančias sritis, apribotas paprastomis uždaromis kreivėmis. Geografiniuose žemėlapiuose empiriškai pastebėta, kad buvo išbandyta daugybė specialių atvejų, kad norint spalvinti regionus reikia ne daugiau kaip keturių spalvų, kad du regionai, turintys bendrą ribą, visada būtų spalvoti skirtingai, o tam tikrais atvejais būtinos bent keturios spalvos. (Regionai, susitinkantys tik viename taške, pavyzdžiui, Kolorado valstija ir Arizonos valstija JAV, nelaikomi turinčiais bendrą ribą). Šio empirinio stebėjimo įforminimas yra tai, kas vadinama „keturių spalvų teorema“. Problema yra įrodyti arba paneigti teiginį, kad taip yra kiekviename plokštuminiame žemėlapyje. Nesunku įrodyti, kad trijų spalvų nepakaks, o penkių spalvų pakankamumą 1890 m. Įrodė britų matematikas PJ Heawood.
1879 m. Anglai AB Kempe pasiūlė keturių spalvų problemos sprendimą. Nors Heawood parodė, kad Kempe argumentai buvo ydingi, vėlesniame tyrime pasirodė dvi jo koncepcijos. Vienas iš jų, vadinamas neišvengiamumu, teisingai nurodo, kad neįmanoma sudaryti žemėlapio, kuriame nėra kiekvienos iš keturių konfigūracijų (šias konfigūracijas sudaro regionas su dviem kaimynais, vienas su trim, vienas su keturiais ir vienas su penkiais). Antroji sąvoka - redukuotumas - yra kilusi iš Kempe pagrįstų įrodymų, kad jei yra žemėlapis, kuriam reikalingos bent penkios spalvos ir kuriame yra regionas su keturiais (arba trim ar dviem) kaimynais, tada turi būti žemėlapis, reikalaujantis penkių spalvos mažesniam regionų skaičiui. Kempe'o bandymas įrodyti žemėlapio, kuriame yra penkios kaimynės, žemėlapio tinkamumą, buvo klaidingas, tačiau jis buvo ištaisytas įrodyme, kurį 1976 m. Paskelbė Kennethas Appelas ir Wolfgangas Hakenas iš JAV. Jų įrodymai sulaukė tam tikros kritikos, nes reikėjo įvertinti 1936 skirtingus atvejus, kiekviename iš kurių buvo atlikta 500 000 loginių operacijų. „Appel“, „Haken“ ir jų bendradarbiai sugalvojo programas, kurios dideliam skaitmeniniam kompiuteriui suteikė galimybę tvarkyti šias detales. Kompiuteriui užduočiai atlikti prireikė daugiau nei 1000 valandų, o gautas oficialus įrodymas yra keli šimtai puslapių.
Eulerio ciklai ir Karaliaučiaus tilto problema
Daugiagrafinį G sudaro netuščias viršūnių rinkinys V (G) ir atskirų V (G) elementų porų rinkinys E (G), kurių dažnis f ≥ 1, pritvirtintas prie kiekvienos poros. Jei pora (x 1, x 2) su dažniu f priklauso E (G), tada viršūnės x 1 ir x 2 yra sujungtos f briaunomis.
Daugiagrafo G euleriškas ciklas yra uždara grandinė, kurioje kiekvienas kraštas pasirodo tiksliai vieną kartą. Euleris parodė, kad multigrafas turi Eulerian ciklą tik tada, kai jis yra sujungtas (išskyrus pavienius taškus), o nelyginio laipsnio viršūnių skaičius yra lygus nuliui arba dviem.
Ši problema pirmiausia iškilo taip. Pregelio upė, susiformavusi iš dviejų jos atšakų santakos, teka per Karaliaučiaus miestą ir teka į abi puses Kneiphofo salą. Kaip parodyta 6A paveiksle, buvo septyni tiltai. Miestiečiai svarstė, ar galima eiti pėsčiomis ir kirsti kiekvieną tiltą tik vieną kartą. Tai prilygsta multilerio, esančio 6B paveiksle, Eulerio ciklo nustatymui. Euleris parodė, kad tai neįmanoma, nes yra keturios nelyginės eilės viršūnės.
