Mis on graafikuteooria ja kuidas graafikut sellisena määratletakse?

1736. aastal täheldati Šveitsi füüsiku-matemaatiku Leonhard Euleri (1707-1783) töö põhjal, et tippude järjestus määratleb tee, aga kui see tee koosneb erinevatest tippudest ilma korduvate servadeta, nimetatakse seda teeks või teeks eulerian; kui lisaks jõuame alguspunkti, läbides iga serva ainult ühe korra, siis on meil Euleri tsükkel (ahel).

Tsitaat (APA)

Aleksander Barraza | juuli. 2022
Füüsika kraad

Omalt poolt määratleme graafiku järjestatud paarina (LÄHEB) kus v tähistab graafi kõigi tippude või sõlmede (mitutühja) hulka, while A tähistab kõigi graafi tippe ühendavate servade või joonte hulka (see võib olla tühi). Komplekti elemendid A saab tähistada järjestamata paarina {v, w}, kus v ja w on elemendid (sõlmed või tipud) v, sel viisil öeldakse siis, et v ja w on külgnevad tipud (neid ühendab serv).

Graafiteooria tuleneb vastusest, mille Euler andis populaarse leidlikkuse probleemile, mis mõtles, kuidas ületada seitset silda, mis ühines Königsbergi kogukonna kahe saarega (tol ajal Saksamaa osa ja praegu Kaliningrad Venemaal), nende vahel ja mandriga, kasutamata kahte korda sama silla ja jõudmine alguspunkti (asub mandril), mis iganes see ka poleks, tehes kindlaks, et sel juhul lõppkokkuvõttes ei võiks.

Königsbergi seitsme silla probleem

Euler modelleeris Königsbergi graafikuna, kus iga punkt (tipp või sõlm) tähistab silda ja iga joon (serv) teed maismaal:

Mis on selle probleemi lahendus?

pole ühtki lahendus mis vastab kehtestatud tingimustele, kuna nagu näitas Euler, ei ole tipud paarisastmega, st paarisarv sirgeid ei mõjuta iga punkti _[3]. Tundub, et me ei saa nii lihtsalt määratletud struktuuriga palju ära teha, nagu see sageli juhtub matemaatika, Mõnikord pole asjad nii, nagu nad paistavad. Seega üks viljakamaid, läbivamaid ja interdistsiplinaarsemaid valdkondi _[4] inimteadmised, graafiteooria.

Euleri graafikud või Euleri trajektooriga?

Kõigil järgmistel graafikutel on Euleri teed _[5]. Kas neil kõigil on Euleri tsüklid?

Võtame kolmanda graafiku:

Nummerdame tipud:

Näeme siis, et jadaga {3,4,6,2,1,3,7,6,5,4,2} määratud tee on Euleri tee, kuna see läbib terve graafiku ilma servade kordamiseta, kuid see ei ole Euleri tsükkel, kuna see ei jõua alguspunkti. Mis oleks juhtunud, kui nummerdaksime tipud erinevalt? Mitte palju, välja arvatud see, et nüüd määraks tee teistsugune järgnevus. Mis oleks juhtunud, kui oleksime järginud teisi teid, kui meie esialgses lahenduses pakutud? Sellele küsimusele on veidi keerulisem vastata ja see hõlmab algoritme, mille üle tarkvarainsenerid tavaliselt rõõmustavad. programmeerimine.

Siin avaldatu täpsemaks tõestuseks peame viitama järgmisele tulemusele:

"Ole G ühendatud graafik _[6]. Siis jah G on a vooluring Euler, iga tipu aste on paaris, samas kui kui G on Euleri tee, G-l on täpselt kaks paaritu astme tippu _[7] (täpselt tipud, kus tee algab ja lõpeb)".

Seejärel saame kontrollida, et tegelikult on meie võetud graafis ainult tippudel 3 ja 6 paaritu aste (see juhtuks isegi siis, kui tippude nummerdamine oleks olnud erinev), seetõttu on sellel graafil tee eulerian _[8]. Ülejäänud graafikute puhul saame jätkata analoogsel viisil ja kontrollida, kas neil on tõepoolest teed ja Euleri tsüklid või teisiti, kas me saame selliseid graafikuid joonistada ilma pliiatsit kätte võtmata ja kordamata read? Vastuse sellele küsimusele võib tuletada juba seni selgitatust, kuid see on harjutus peenmotoorika, leidlikkuse ja kannatlikkuse poolest huvitav, kutsun lugejat üles leidma ja joonistama 6 või enama graafiku tipud koos trajektoor Eulerian.

Kas on ka teist tüüpi graafikuid? Kas graafiteoorial on rakendusi "päris" maailmas?

Need graafikud, mida oleme väga lühidalt üle vaadanud, on vaid üks paljudest graafitüüpidest, mida graafiteoorias leiame. Samuti võime leida selliseid graafikuid nagu puud, mis on väga representatiivsed kogumites, kus nende elemente saab klassifitseerida hierarhiatesse ning loendusarvutustes ja tõenäosus_[9], digraafid, Hamiltoni graafikud _[10], jne.

Pilt graafilistest mudelitest ja võrkudest ajakirjas Psycho., autor Ruiz, Ana María.

Need mõistatused, kui tahame neid nii nimetada, on tänapäeva maailmas tohutult rakendatavad nii erinevates olukordades nagu: bioloogia molekulaarne _[11], andmetöötlus_[12], telekommunikatsioon _[13] ja võrguanalüüs _[14]. Tasub siis küsida: kas pole vähemalt uudishimulik, et probleem on peaaegu banaalne on lõpuks matemaatika üks huvitavamaid ja silmatorkavamaid tulemusi? Võib-olla oli selleks vaja inimkonna ühe silmapaistvama mõistuse panust.