Grafi kub

Nga Wikipedia, enciklopedia e lirë

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[Redakto | Redakto nëpërmjet kodit]

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.[1]

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][2]

Problemi i urave të Königsberg[Redakto | Redakto nëpërmjet kodit]

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.[3]

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.[4]

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.[5]

3. Algjebra e grafeve trevalente me nyje[Redakto | Redakto nëpërmjet kodit]

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.[6][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][7]

Numërimi i grafeve trevalante me nyje[Redakto | Redakto nëpërmjet kodit]

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.[8]

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[Redakto | Redakto nëpërmjet kodit]

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.[9]

Vetitë algjebrike[Redakto | Redakto nëpërmjet kodit]

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

Grafi Tetrahedral[Redakto | Redakto nëpërmjet kodit]

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

dhe numri kromatik 4. Është planar dhe kub simetrik.

Grafiku tetrahedral është një graf integral me spektër grafik . Grupi i tij i automorfizmit ka rregull

[10]

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.

  1. ^ Wilson, Robin J. (2013-12-17). History of Graph Theory (në anglisht). Routledge Handbooks Online. doi:10.1201/b16132-3. ISBN 978-1-4398-8018-0.
  2. ^ "Cubic symmetric graphs". web.archive.org. 2011-10-23. Arkivuar nga origjinali më 23 tetor 2011. Marrë më 2022-02-08. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)Mirëmbajtja CS1: BOT: Gjendja e adresës origjinale është e panjohur (lidhja)
  3. ^ Weisstein, Eric W. "Königsberg Bridge Problem". mathworld.wolfram.com (në anglisht). Marrë më 2022-02-08.
  4. ^ "graph theory - Euler's Solution of Seven Bridges of Königsberg in Layman Terms". Mathematics Stack Exchange. Marrë më 2022-02-08. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)
  5. ^ "Königsberg bridge problem | mathematics | Britannica". www.britannica.com (në anglisht). Marrë më 2022-02-08.
  6. ^ {{cite web}}: Burim bosh (Ndihmë!)Mirëmbajtja CS1: Gjendja e adresës (lidhja)
  7. ^ (PDF) http://www.imar.ro/~mbuliga/graphic.pdf. {{cite web}}: Mungon ose është bosh |title= (Ndihmë!); Mungon ose është bosh parametri |language= (Ndihmë!)Mirëmbajtja CS1: Gjendja e adresës (lidhja)
  8. ^ Weisstein, Eric W. "Cubic Graph". mathworld.wolfram.com (në anglisht). Marrë më 2022-02-08.
  9. ^ "Klein graphs". Wikipedia (në anglisht). 2021-10-19.
  10. ^ Weisstein, Eric W. "Tetrahedral Graph". mathworld.wolfram.com (në anglisht). Marrë më 2022-02-08.