Mga aplikasyon ng teorya ng grapiko
Mga graph ng planar
Ang isang graph G ay sinasabing planar kung maaari itong irepresenta sa isang eroplano sa isang fashion na ang mga vertice ay lahat ng magkakaibang mga puntos, ang mga gilid ay simpleng mga curves, at walang dalawang gilid ang magkita sa isa't isa maliban sa kanilang mga terminal. Halimbawa, ang K 4, ang kumpletong graph sa apat na mga vertice, ay planar, tulad ng ipinapakita ng Figure 4A.
Ang dalawang mga graph ay sinasabing homeomorphic kung ang parehong maaaring makuha mula sa parehong graph sa pamamagitan ng mga subdibisyon ng mga gilid. Halimbawa, ang mga graph sa Figure 4A at Figure 4B ay homeomorphic.
Ang K m, n grap ay isang graph kung saan ang vertex set ay maaaring nahahati sa dalawang subset, ang isa ay may m vertice at ang isa ay may n vertices. Anumang dalawang patayo ng parehong subset ay nonadjacent, samantalang ang alinman sa dalawang patayo ng magkakaibang mga subset ay katabi. Ang Polish matematiko na si Kazimierz Kuratowski noong 1930 ay nagpatunay sa sumusunod na kilalang teorema:
Ang isang kinakailangan at sapat na kondisyon para sa isang graph G upang maging planar ay hindi ito naglalaman ng isang subgraph homeomorphic sa alinman sa K 5 o K 3,3 na ipinakita sa Larawan 5.
Ang isang pang-elementong pag-urong ng isang graph G ay isang pagbabagong-anyo ng G sa isang bagong graph G 1, tulad ng dalawang katabing vertice u at υ ng G ay pinalitan ng isang bagong vertex w sa G 1 at w ay katabi sa G 1 sa lahat ng mga patas na alinman sa u o υ ay katabi sa G. Ang isang graph G * ay sinasabing isang pag-urong ng G kung ang G * ay maaaring makuha mula sa G sa pamamagitan ng isang pagkakasunod-sunod ng mga pangungunang elementarya. Ang sumusunod ay isa pang katangian ng isang planar graph dahil sa Aleman na matematika na si K. Wagner noong 1937.
Ang isang graph ay planar kung at lamang kung ito ay hindi nakontrata sa K 5 o K 3,3.
Ang apat na kulay na problema sa mapa
Para sa higit sa isang siglo ang solusyon ng apat na kulay na problema sa mapa ay humiwalay sa bawat analyst na sinubukan ito. Ang problema ay maaaring maakit ang atensyon ni Möbius, ngunit ang unang nakasulat na sanggunian ay tila isang liham mula sa isang Francis Guthrie sa kanyang kapatid, isang mag-aaral ni Augustus De Morgan, noong 1852.
Ang problema ay may kinalaman sa mga mapa ng eroplano - iyon ay, mga subdibisyon ng eroplano sa mga rehiyon ng nonoverlapping na nakatali sa pamamagitan ng mga simpleng saradong kurba. Sa mga mapa ng heograpiya ay napansin ang empirikal, sa maraming mga espesyal na kaso na sinubukan, na, sa karamihan, apat na mga kulay ang kinakailangan upang kulayan ang mga rehiyon upang ang dalawang rehiyon na nagbabahagi ng isang karaniwang hangganan ay palaging may kulay na magkakaiba, at sa ilang mga kaso na hindi bababa sa apat na kulay ay kinakailangan. (Ang mga rehiyon na nakakatugon lamang sa isang punto, tulad ng mga estado ng Colorado at Arizona sa Estados Unidos, ay hindi itinuturing na magkaroon ng isang karaniwang hangganan). Ang isang pormalisasyon ng empirical na pagmamasid na ito ay bumubuo ng tinatawag na "ang apat na kulay na teorema." Ang problema ay upang patunayan o hindi masabi ang assertion na ito ang kaso para sa bawat mapa ng planar. Na ang tatlong kulay ay hindi sapat ay madaling ipakita, samantalang ang sapat na limang kulay ay napatunayan noong 1890 ng British matematika na si PJ Heawood.
Noong 1879, si AB Kempe, isang Englishman, ay nagpanukala ng isang solusyon ng apat na kulay na problema. Bagaman ipinakita ni Heawood na ang pagtatalo ni Kempe ay mali, dalawa sa mga konsepto nito ang nagpatunay ng mabunga sa pag-iimbestiga. Ang isa sa mga ito, na tinawag na hindi maiiwasan, tama na sinasabi ang imposibilidad ng pagtatayo ng isang mapa kung saan ang bawat isa sa apat na mga pagsasaayos ay wala (ang mga pagsasaayos na ito ay binubuo ng isang rehiyon na may dalawang kapitbahay, isa na may tatlo, isa na may apat, at isa na may lima). Ang pangalawang konsepto, ng reducibility, ay kumukuha ng pangalan nito mula sa wastong patunay ng Kempe na kung mayroong isang mapa na nangangailangan ng hindi bababa sa limang mga kulay at naglalaman ng isang rehiyon na may apat (o tatlo o dalawa) na kapitbahay, kung gayon dapat mayroong mapa na nangangailangan ng limang mga kulay para sa isang mas maliit na bilang ng mga rehiyon. Ang pagtatangka ni Kempe na patunayan ang muling pagbabalik ng isang mapa na naglalaman ng isang rehiyon na may limang kapitbahay ay mali, ngunit naayos ito sa isang patunay na inilathala noong 1976 nina Kenneth Appel at Wolfgang Haken ng Estados Unidos. Ang kanilang patunay ay nakakaakit ng ilang kritisismo dahil kinakailangan nito ang pagsusuri ng 1,936 natatanging mga kaso, ang bawat isa ay nagsasangkot ng 500,000 lohikal na operasyon. Ang Appel, Haken, at ang kanilang mga nakikipagtulungan ay naglikha ng mga programa na posible para sa isang malaking digital computer upang hawakan ang mga detalyeng ito. Ang computer ay nangangailangan ng higit sa 1,000 oras upang maisagawa ang gawain, at ang nagresultang pormal na patunay ay ilang daang pahina ang haba.
Eulerian cycle at ang problema sa tulay ng Königsberg
Ang isang multigraph G ay binubuo ng isang di-walang laman na set V (G) ng mga vertice at isang subset E (G) ng hanay ng mga hindi nakaayos na mga pares ng mga natatanging elemento ng V (G) na may dalas na f ≥ 1 na nakakabit sa bawat pares. Kung ang pares (x 1, x 2) na may dalas f ay nabibilang sa E (G), kung gayon ang mga vertices x 1 at x 2 ay sumali sa pamamagitan ng f gilid.
Ang isang Eulerian cycle ng isang multigraph G ay isang saradong kadena kung saan ang bawat gilid ay lilitaw nang eksakto nang isang beses. Ipinakita ni Euler na ang isang multigraph ay nagtataglay ng isang Eulerian cycle kung at kung ito ay konektado (bukod sa mga hiwalay na puntos) at ang bilang ng mga vertice ng kakaibang degree ay alinman sa zero o dalawa.
Ang problemang ito ay unang lumabas sa sumusunod na paraan. Ang Ilog Pregel, na nabuo sa pamamagitan ng pagkakaugnay sa dalawang sanga nito, ay dumadaloy sa bayan ng Königsberg at dumadaloy sa magkabilang panig ng isla ng Kneiphof. Mayroong pitong tulay, tulad ng ipinapakita sa Figure 6A. Ang bayan ng bayan ay nagtaka kung posible bang maglakad-lakad at tumawid sa bawat tulay nang isang beses lamang. Katumbas ito sa paghahanap ng isang Eulerian cycle para sa multigraph sa Figure 6B. Ipinakita ito ni Euler na imposible dahil mayroong apat na patayo ng kakaibang pagkakasunud-sunod.
