Grafa teorijas pielietojumi
Plakanie grafiki
G grafu G uzskata par plakanu, ja to var attēlot plaknē tādā veidā, ka visas virsotnes ir atšķirīgi punkti, malas ir vienkāršas līknes un neviena no divām malām nesatur viena otru, izņemot to galos. Piemēram, K 4, viss četru virsotņu grafiks, ir plānots, kā parādīts 4A attēlā.
Divi grafiki tiek uzskatīti par homeomorfiem, ja abus no viena un tā paša grafika var iegūt, sadalot malas. Piemēram, diagrammas 4A un 4B attēlos ir homeomorfiskas.
K m, n grafiks ir grafiks, kuram virsotņu kopu var sadalīt divās apakšgrupās, vienā ar m virsotnēm, otrā - ar n virsotnēm. Jebkuras vienas un tās pašas apakškopas virsotnes nav blakus, turpretī jebkuras divas dažādu apakšgrupu virsotnes atrodas blakus. Poļu matemātiķis Kazimierz Kuratowski 1930. gadā pierādīja šādu slaveno teorēmu:
Nepieciešams un pietiekams nosacījums, lai grafiks G būtu plāns, ir tāds, ka tajā nav 5. attēlā parādīta apakšgrāfa homeomorfiskas vērtības ne ar K 5, tā ar K 3,3.
Elementāru kontrakcijas diagrammas G ir transformācija G ar jaunu grafiku G 1, tā, ka divas blakus virsotnes u un υ no G tiek aizstāts ar jaunu virsotne w G 1 un w ir blakus G 1 visiem virsotnes līdz kas vai nu u, vai υ ir blakus G. Grafiks G * tiek uzskatīts par G saraušanos, ja G * no G var iegūt ar elementāru sašaurinājumu secību. Šis ir vēl viens plāna grafika raksturojums, pateicoties vācu matemātiķim K. Vāgneram 1937. gadā.
Diagramma ir plakana tikai tad, ja tā nav sašaurināma ar K 5 vai K 3,3.
Četru krāsu kartes problēma
Vairāk nekā gadsimtu četru krāsu kartes problēmas risinājums izvairījās no katra analītiķa, kurš to mēģināja. Iespējams, ka šī problēma piesaistīja Möbius uzmanību, taču pirmā rakstiskā atsauce uz to, šķiet, ir viena Franciska Gutrī vēstule viņa brālim, Augusta De Morgana studentam, 1852. gadā.
Problēma attiecas uz plakanām kartēm, tas ir, uz plaknes dalīšanu reģionos, kas nepārklājas, un tos ierobežo vienkāršas slēgtas līknes. Ģeogrāfiskajās kartēs empīriski ir novērots, tik daudzos īpašos gadījumos, cik izmēģināts, ka reģionu krāsošanai ir vajadzīgas vismaz četras krāsas, lai divi reģioni, kuriem ir kopīga robeža, vienmēr būtu krāsaini atšķirīgi. dažos gadījumos ir vajadzīgas vismaz četras krāsas. (Uzskata, ka reģioniem, kas satiekas tikai vienā punktā, piemēram, Kolorādo un Arizonas štatiem Amerikas Savienotajās Valstīs, nav kopēju robežu). Šī empīriskā novērojuma formalizēšana veido tā saukto “četrkrāsu teorēmu”. Problēma ir pierādīt vai atspēkot apgalvojumu, ka tas tā ir katrai planētas kartei. To, ka ar trim krāsām nepietiks, var viegli pierādīt, turpretī piecu krāsu pietiekamību 1890. gadā pierādīja britu matemātiķis PJ Heawood.
1879. gadā anglis AB Kempe ierosināja četrkrāsu problēmas risinājumu. Lai arī Heawood parādīja, ka Kempe arguments bija kļūdains, vēlāk divi pētījumi izrādījās auglīgi. Viens no tiem, ko sauc par nenovēršamību, pareizi norāda uz neiespējamību izveidot karti, kurā nav katras no četrām konfigurācijām (šīs konfigurācijas sastāv no reģiona ar diviem kaimiņiem, vienu ar trim, vienu ar četriem un vienu ar pieciem). Otrais jēdziens, kas ir reducējamība, ir cēlies no Kempe derīga pierādījuma, ka, ja ir karte, kurai ir vajadzīgas vismaz piecas krāsas un kurā ir reģions ar četriem (vai trim vai diviem) kaimiņiem, tad jābūt arī kartei, kurai nepieciešami pieci krāsas mazākam reģionu skaitam. Kempe mēģinājums pierādīt kartes, kurā ir pieci kaimiņvalstis, rediģējamību, bija kļūdains, taču tas tika labots pierādījumā, ko 1976. gadā publicēja Kenneth Appel un Wolfgang Haken no Amerikas Savienotajām Valstīm. Viņu pierādījumi izraisīja zināmu kritiku, jo bija nepieciešams novērtēt 1936 atsevišķus gadījumus, no kuriem katrs bija saistīts ar 500 000 loģiskām operācijām. Appel, Haken un viņu līdzstrādnieki izstrādāja programmas, kas ļāva lielam digitālajam datoram rīkoties ar šīm detaļām. Datoram uzdevuma veikšanai bija vajadzīgas vairāk nekā 1000 stundas, un iegūtais oficiālais pierādījums ir vairākus simtus lappušu garš.
Eulera cikli un Kēnigsbergas tilta problēma
Daudzgrāfs G sastāv no tukša virsotņu kopa V (G) un no atsevišķiem V (G) elementu nesakārtotu pāru kopas E (G) ar frekvenci f ≥ 1, kas piestiprināta katram pārim. Ja pāris (x 1, x 2) ar frekvenci f pieder pie E (G), tad virsotnes x 1 un x 2 savieno ar f malām.
Daudzgrāfa G Eulerian cikls ir slēgta ķēde, kurā katra mala parādās precīzi vienreiz. Eulers parādīja, ka multigrāfam piemīt Eulera cikls tikai tad, ja tas ir savienots (izņemot atsevišķus punktus) un nepāra grādu virsotņu skaits ir nulle vai divas.
Vispirms šī problēma radās šādi. Pregelas upe, ko veido divu atzaru saplūšana, ved cauri Kēnigsbergas pilsētai un plūst abpus Kneiphofas salai. Bija septiņi tilti, kā parādīts 6.A attēlā. Pilsētnieki domāja, vai ir iespējams pastaigāties un šķērsot katru tiltu tikai vienu reizi. Tas ir līdzvērtīgs Eulera cikla atrašanai multigrāfam 6.B attēlā. Eulers parādīja, ka tas nav iespējams, jo ir četras nepāra kārtas virsotnes.
