Grafi kub

Në fushën matematikore të teorisë së grafikëve, një graf kub është një graf në të cilin të gjitha kulmet kanë shkallën tre. Me fjalë të tjera, një grafik kub është një graf me 3 kulme të rregullta. Grafikët kub quhen edhe grafikë trevalent.

Historia

Megjithëse përmendja e parë e një grafiku nuk ishte deri në vitin 1878, idetë teorike të grafikut mund të gjurmohen në 1735 kur Leonhard Euler (1707–83) prezantoi zgjidhjen e tij të problemit të urave të Königsberg.

Ronald M. Foster filloi të mbledhë ekzemplarë të grafikëve të vegjël simetrikë kub përpara vitit 1934, duke mbajtur një regjistrim të të gjithë grafikëve të tillë. Në vitin 1988 versioni i atëhershëm aktual i regjistrimit u publikua nga I.Z. Bouwer, W.W. Chernoff, B. Monson dhe Z. Star në një libër të titulluar The Foster Census (Charles Babbage Research Centre, 1988). dhe përmbante të dhëna për grafikët deri në 512 kulme.

Ky libër renditi ndërtimet e shumicës së grafikëve dhe të dhëna të ndryshme në lidhje me grafikët, por nuk i renditi në mënyrë eksplicite vetë grafikët.

Qëllimi kryesor i këtij arkivi është të japë listimet e qarta të grafikëve, me shpresën se kjo do të jetë e dobishme për studiuesit.

Për të maksimizuar dobinë e këtyre të dhënave, ne kemi miratuar një skemë emërtimi në përputhje me atë të përdorur në The Foster Census. Kështu për shembull, grafiku F240B është grafiku 240B i Regjistrimit Foster, dhe grafiku F126A është grafiku 126 i Regjistrimit Foster.

Regjistrimi origjinal Foster ishte jashtëzakonisht i plotë, në atë që humbi vetëm disa grafikë në nën 512 kulme. Këta grafikë janë F480B, F432E, F448C, F480C, F480D, F486D, F512D, F512E, F512F, F512G.[1]

Problemi i urave të Königsberg

Problemi i urës Königsberg, një enigmë matematikore rekreative, e vendosur në qytetin e vjetër prusian të Königsberg (tani Kaliningrad, Rusi), që çoi në zhvillimin e degëve të matematikës të njohura si topologji dhe teori grafike.

Ky problemi i urës pyet nëse shtatë urat e qytetit të Königsberg, mbi lumin Preger mund të përshkohen të gjitha në një udhëtim të vetëm pa u dyfishuar, me kërkesën shtesë që udhëtimi të përfundojë në të njëjtin vend ku filloi. Kjo është e barabartë me pyetjen nëse multigrafi në katër nyje dhe shtatë skaje ka një cikël Eulerian. Ky problem iu përgjigj negativisht nga Euler (1736), dhe përfaqësonte fillimin e teorisë së grafeve.

2.1. Problemi i urave të Königsberg,

2.2. Problemi i urave të Königsberg i dhënë si graf.

Në vitin 1735, matematikani zviceran Leonhard Euler paraqiti një zgjidhje për këtë problem, duke arritur në përfundimin se një shëtitje e tillë ishte e pamundur. Për ta konfirmuar këtë, supozoni se një shëtitje e tillë është e mundur. Në një takim të vetëm me një masë të caktuar tokësore, përveç asaj fillestare ose përfundimtare, duhen llogaritur dy ura të ndryshme: një për hyrjen në tokë dhe një për daljen nga ajo. Kështu, çdo masë e tillë tokësore duhet të shërbejë si një pikë përfundimtare e një numri urash të barabartë me dyfishin e numrit të rasteve që haset gjatë ecjes. Prandaj, çdo masë tokësore, me përjashtim të mundshëm të atyre fillestare dhe fundore nëse nuk janë identike, duhet të shërbejë si pikë fundore e një numri çift urave. Megjithatë, për masat tokësore të Königsberg, A është një pikë fundore e pesë urave, dhe B, C dhe D janë pika fundore të tre urave. Prandaj, shëtitja është e pamundur.

3. Algjebra e grafeve trevalente me nyje

Grafikët trevalent me nyje; Knotted Trivalent Graphs (KTG) formojnë një algjebër të pasur me disa operacione të thjeshta: shuma e lidhur, zbërthimi dhe flluskimi (bubbling) . Me këto operacione, KTG-të krijohen nga shiritat katërkëndor të panyjëzuar dhe M¨obius. Shumë paraqitje të njohura më parë të nyjeve, duke përfshirë diagramet e nyjeve dhe ngatërresat jo-shoqëruese, mund të shndërrohen në prezantime të KTG në një mënyrë të natyrshme.

Shpesh dy sekuenca të operacioneve KTG prodhojnë të njëjtin rezultat në të gjitha hyrjet. Këto marrëdhënie "elementare" mund të jenë delikate: për shembull, ekziston një algjebër planare e KTG-ve me një cikël të dalluar.[2]

Një graf i orientuar është një çift (V, E), me V bashkësinë e nyjeve dhe E ⊂ V × V bashkësinë e skajeve. Le të shënojmë me α : V → 2^E hartën që i bashkon çdo nyje N ∈ V bashkësinë e brinjëve ngjitur α(N). Në këtë punim ne punojmë me grafikë lokalisht planarë me nyje të zbukuruara, d.m.th. do t'i bashkëngjisim një grafiku (V, E) informacion shtesë:

- një funksion f : V → A që lidh me çdo nyje N ∈ V një element të "alfabetit grafik" A ,

- një rend ciklik i α(N) për çdo N ∈ V , i cili është i barabartë me dhënien e një ngulitjeje lokale të nyjës N dhe skajeve ngjitur me të në rrafsh.[3]

Numërimi i grafeve trevalante me nyje

Grafikët kub në n nyje ekzistojnë vetëm për n çift. Grafikët kub jo domosdoshmërisht të lidhur në n=4, 6 dhe 8 janë ilustruar më sipër. Një numërim i grafikëve kub në n nyje për n të vogla zbatohet në gjuhën Wolfram si GraphData["Cubic", n].

Një kriter i domosdoshëm (por jo i mjaftueshëm) që një grafik të jetë kub është ai m/n=3/2, ku m është numërimi i skajeve dhe n është numri i kulmeve.

Numrat e grafikëve kub jo domosdoshmërisht të lidhur në nyjet 2, 4, 6, ... janë 0, 1, 2, 6, 21, 94, 540, 4207, ... . Grafiku unik kub me 4 nyje është grafiku i plotë K_4 (grafi tetraedral). Dy grafikët kubikë me 6 nyje janë grafikët qarkullues Ci_(1,3)(6) (grafi i dobisë) dhe Ci_(2,3)(6). Tre nga gjashtë grafikët kubikë me 8 nyje janë grafikët kub dhe grafikët qarkullues Ci_(1,4)(8) dhe Ci_(2,4)(8).

Grafikët kub të lidhur janë përcaktuar nga Brinkmann (1996) deri në 24 nyje, dhe numrat e grafikëve të tillë për n=2, 4, ... janë 0, 1, 2, 5, 19, 85, 509, 4060, 41301, ... (OEIS A002851). Meringer dhe Royle mbajnë në mënyrë të pavarur numërimet e grafikëve kub të lidhur.

(3,g)-grafikët e kafazit janë kub. Përveç kësaj, tabelat e mëposhtme japin disa grafikë të emërtuar që janë skelete poliedrikësh.

4.1. skelete poliedrikësh

grafiku	nyjet
grafiku katërkëndor	4
grafiku kub	8
grafiku tetraedral i cunguar	12
grafiku dodekaedral	20
grafiku kub i cunguar	24
grafiku oktaedral i cunguar	24
grafiku rombikuboktedral i madh	48
grafiku dodekaedral i cunguar	60
grafiku ikozaedral i cunguar	60
grafiku - 96 i Horton	96
grafiku i madh rombikosidodekaedral	120
Tutte 12-kafaz	126

5. Grafi Klein

5.1. Grafi Klein

Është një grafik Hamiltonian. Ai ka numrin kromatik 3, indeksin kromatik 3, rrezen 6, diametrin 6 dhe perimetrin 7. Është gjithashtu një graf i lidhur me 3 kulme dhe një graf me 3 tehe. Ka trashësinë e librit 3 dhe radhën numër 2.

Mund të futet në sipërfaqen e orientueshme të gjinisë 3 (e cila mund të përfaqësohet si kuartic Klein), ku formon "hartën Klein" me 24 faqe shtatëkëndore, simboli Schläfli {7,3}8.

Sipas regjistrimit të Fosterit, grafiku Klein, i referuar si F056B, është i vetmi grafik simetrik kub në 56 kulme, i cili nuk është dypalësh.

Mund të rrjedhë nga grafiku Coxeter me 28 kulme.

Vetitë algjebrike

Grupi i automorfizmit të grafikut Klein është grupi PGL2(7) i rendit 336, i cili ka PSL2(7) si një nëngrup normal. Ky grup vepron në mënyrë kalimtare në gjysmë skajet e tij, kështu që grafi Klein është një graf simetrik.

Polinomi karakteristik i këtij grafi Klein me 56 kulme është i barabartë me

$x^{7}(x-3)(x+2)^{6}(x^{2}-2)^{6}(x^{2}-x-4)^{7}(x^{2}-2x-1)^{8}$

Grafi Tetrahedral

Grafiku tetraedral është grafiku platonik që është grafiku unik poliedrik në katër nyje, i cili është gjithashtu grafiku i plotë K_4 dhe për rrjedhojë edhe grafiku i rrotave W_4. Ai zbatohet në gjuhën Wolfram si GraphData ["TetrahedralGraph"].

6.1. Grafi tetrahedral

Përfshirja integrale planare minimale e grafikut tetraedral (figura 5.1.), ka gjatësinë maksimale të skajit prej 17 (Harborth et al. 1987). Grafiku tetrahedral është gjithashtu i këndshëm (Gardner 1983, fq. 158 dhe 163-164).

Grafiku tetraedral ka 4 nyje, 6 skaje, lidhshmëri kulmore 4, lidhshmëri e skajit 3, diametri i grafikut 1, rreze grafiku 1 dhe perimetri 3. Ka polinom kromatik

$\pi (z)=z(z-1)(z-2)(z-3)=z^{4}-6z^{3}+11z^{2}-6z$ dhe numri kromatik 4. Është planar dhe kub simetrik.

Grafiku tetrahedral është një graf integral me spektër grafik $Spec(G)=(-1)^{3}3^{1}$ . Grupi i tij i automorfizmit ka rregull

$|Aut(G)|=24.$

Grafiku tetrahedral është grafiku i vijës së grafikut yjor S_5, dhe grafiku i linjës i grafikut tetraedral është grafiku tetëedral.

6.2. Matrica e afërsisë

6.3. Matrica e incidencës

Grafikët në 6.2 - 6.4 tregojnë matricat e afërsisë, incidencës dhe distancës grafike për grafikun tetraedral.

Grafiku dypalësh i grafikut tetraedral është grafiku kub.

6.4. Matric e distances

Në përgjithësi, një graf Johnson i nga J(n,3) (me n>=6) njihet si një graf n-tetrahedral. Grafiku 6-tetraedral është një graf i rregullt në distancë me varg kryqëzimi {9,4,1;1,4,9}, dhe për rrjedhojë edhe një graf Taylor.