Graafiku mõiste ajaloos. Graafiteooria

Leonard Eulerit peetakse graafiteooria rajajaks. 1736. aastal sõnastab ta ühes oma kirjas ja pakub välja lahenduse seitsme Königsbergi silla probleemile, millest hiljem sai üks klassikalised probleemid graafikuteooria.

Esimesed graafikuteooria ülesanded olid seotud matemaatiliste meelelahutusülesannete ja mõistatuste lahendamisega. Siin on ümberjutustus Euleri 13. märtsi 1736 kirjast: „Mulle esitati probleem Königsbergi linnas asuva saare kohta, mida ümbritseb 7 sillaga jõgi. Küsimus on selles, kas keegi suudab neist pidevalt ümber sõita, läbides iga silla vaid korra. Ja siis teatati mulle, et keegi pole veel suutnud seda teha, kuid keegi pole tõestanud, et see on võimatu. See küsimus, kuigi triviaalne, tundus mulle siiski tähelepanu vääriv, kuna selle lahendamiseks ei piisa ei geomeetriast, algebrast ega kombinatoorsest kunstist. Pärast pikka mõtlemist leidsin täiesti veenval tõendil põhineva lihtsa reegli, mille abil on võimalik kõigi sedalaadi ülesannete puhul kohe kindlaks teha, kas sellist ümbersõitu saab teha suvalise arvu ja suvalise arvu kaudu. sillad mis tahes või mitte. Königsbergi sildu saab skemaatiliselt kujutada järgmiselt:

Euleri reegel:

1. Graafis, millel pole paaritu astme tippe, toimub kõigi servade läbimine (ja iga serva läbitakse täpselt üks kord), alustades graafi suvalisest tipust.

2. Graafis, millel on kaks ja ainult kaks paaritu kraadiga tippu, toimub läbimine, mis algab ühest tipust paaritu aste ja lõpp teisele.

3. Graafis, millel on rohkem kui kaks paaritu kraadiga tippu, sellist läbimist ei eksisteeri.

Graafikutel reisimisega on seotud teist tüüpi probleem. Me räägime probleemidest, mille puhul on vaja leida tee, mis läbib kõiki tippe ja mitte rohkem kui üks kord läbi iga. Tsüklit, mis läbib iga tippu üks kord ja ainult üks kord, nimetatakse Hamiltoni jooneks (William Rowan Hamiltoni järgi, eelmise sajandi kuulsa Iiri matemaatiku järgi, kes oli esimene selliste joonte uurimine). Kahjuks pole veel leitud üldist kriteeriumi, mille abil saaks otsustada, kas antud graaf on Hamiltoni ja kui on, siis leida sellelt kõik Hamiltoni read.

Formuleeritud 19. sajandi keskel. Nelja värvi probleem tundub samuti meelelahutusliku probleemina, kuid selle lahendamise katsed on viinud mõningate graafikute uurimiseni, millel on teoreetiline ja rakendatud väärtus. Nelja värvi probleem on sõnastatud järgmiselt: "Kas iga tasapinnalise kaardi ala saab värvida nelja värviga nii, et kaks külgnevat ala on värvitud erinevate värvidega?" Hüpotees, et vastus on jaatav, sõnastati 19. sajandi keskel. 1890. aastal tõestati nõrgem väide, et iga tasapinnalist kaarti saab värvida viie värviga. Seoses mis tahes tasapinnalise kaardi selle kahetasandilise graafikuga, saame ülesande samaväärse sõnastuse graafikute kujul: Kas vastab tõele, et iga tasapinnalise graafi kromaatiline arv on väiksem kui neli või sellega võrdne? Arvukad katsed probleemi lahendada mõjutasid mitmete graafiteooria valdkondade arengut. 1976. aastal teatati probleemile positiivsest lahendusest arvuti abil.

Veel üks vana topoloogiline probleem, mis on pikka aega olnud lahendusele eriti vastupidav ja mis on kummitanud mõistatustehuvilisi, on tuntud kui "elektri-, gaasi- ja veevarustusprobleem". 1917. aastal andis Henry E. Dudeney sellele selle sõnastuse. Igas kolmes joonisel kujutatud majas tuleb paigaldada gaas, elekter ja vesi.

Graafiteooria. 1

Graafiteooria tekkelugu. 1

Euleri reegel. 1

Kirjandus

1. Belovi graafikuteooria, Moskva, "Teadus", 1968.

2. Uued pedagoogilised ja infotehnoloogia E.S. Polat , Moskva, "Akadeemia" 1999. aasta

3. Kuznetsov O.P., Adelson-Velski G.M. Diskreetne matemaatika insenerile. – M.: Energoatomizdat, 1988.

4. Cook D., Baze G. Arvutimatemaatika. – M.: Teadus, 1990.

5. Nefedov V.N., Osipova V.A. Diskreetse matemaatika kursus. – M.: Kirjastus MAI, 1992.

6. Ore O. Graafiteooria. – M.: Teadus, 1980.

7. Ismagilov R.S., Kalinkin A.V. Kursuse praktiliste tundide materjalid: Diskreetne matemaatika

saksa keel Graf), aadlitiitel. Venemaal tutvustas Peeter I (B.P. Šeremetev sai selle esimesena 1706. aastal). 19. sajandi lõpus. arvesse võeti üle 300 krahvipere. Likvideeriti Ülevenemaalise Kesktäitevkomitee ja Rahvakomissaride Nõukogu 11. novembri 1917 määrusega.

Suurepärane määratlus

Mittetäielik määratlus ↓

Graafik

Anton (Graf, Anton) 1736, Winterthur - 1813, Dresden. Saksa maalikunstnik. Ta õppis aastatel 1753–1756 I. W. Schellenbergi juures Winterthuris, seejärel I. Ya. Hyde’i juures Augsburgis. Ta töötas portreemaalijana Regensburgis, Winterthuris, Augsburgis, Münchenis, Zürichis. Aastast 1766 - õukonnakunstnik Dresdenis. Alates 1789. aastast - Dresdeni Kunstiakadeemia professor. Berliini, Viini ja Müncheni kunstiakadeemiate liige. Reisinud palju Saksamaal ja Šveitsis. Ta oli portreemaalija, maalis ka maastikke ja tegeles miniatuuridega. Kunstniku varased tööd on teostatud tseremoniaalse barokkportreepildi traditsiooni järgi. Preisimaa kuningapalee aadlike isikute kujutised on täis pidulikkust ja esinduslikkust Preisimaa printsi Fredericki (1777-1778), Preisimaa printsessi Frederica (1787), Preisimaa kuninga Frederick William II (1788) portreedel. , kõik - Berliin, Charlottenburg). Tugev chiaroscuro ja soe värvilahendus näitavad noore kunstniku kirge Rembrandti stiili vastu. 1780-1790ndatel maalis krahv sageli maastiku taustal modelle, mis mõnevõrra pehmendas tema portreede pinget ja staatilisi kujundeid ( Henry VIII, 1804, Saksamaa, erakogu; I. F. von Tilman, Nürnberg, Saksa kodanik. muuseum). Ajastu neoklassikaliste maitsete vaimus kujutab ta iidsete graatsiatena kujutatuid maastikul (Frederica Hillendorff, 1803, Saksamaa, erakogu). Kunstnikule lähedaste inimeste portreed annavad sügavamalt edasi nende sisemist seisundit: kunstnik K. K. Lunwig (1808, Hamburg, Kunsthalle), lüürilised naisepildid - Louise Elisabeth Funk (1790, Leipzig, muuseum kaunid kunstid), Caroline Susanna Graf (1805, Hamburg, Kunsthalle). Peen valguse ja varju modelleerimine rõhutab figuuride selget plastilisust, mis on omane krahvi kujutistele. Figuuri ümbritsev õhuline sfumato annab tunnistust 18. sajandi inglise portreetehnikate uurimisest. Valgustusajastu silmapaistvate tegelaste portreed - S. Gessner (1765-1766, Zürich, Kunsthalle), G. E. Lessing (1771, Leipzig, ülikooli raamatukogu), K. M. Wieland (1794, Weimar, Goethe muuseum), I. G. Sulzer (1771,,) Kunsthalle) - võib-olla kõige olulisem asi, mille kunstnik on loonud. Kunstniku äia, kuulsa saksa filosoofi, esteetika ja matemaatiku I. G. Sulzeri ning Šveitsi poeedi, luulekogu „Idüllid” (1756) autori S. Gessneri portreedel kasutab krahv baroki skeemi. portree, kujutades modelle näiliselt katkenud liikumise hetkel. Tõeline valgustusajastu kunstnik, krahv püüab paljastada rahva kultuuripärandiks saanud inimeste vaimsust ja säravat meelt. Portreed on maalitud tumedale taustale, nagu ka mitmed teised hilisemad tööd (H. I. Medem, 1796; G. L. Gogel, 1796, mõlemad Peterburi, Riikliku Ermitaaži muuseum). Huvi pildi psühholoogiliselt süvendatud arendamise vastu on omane ka kunstniku autoportreedele. Varastel autoportreedel 1765 (New York, Historical Society) ja 1766 (Dresden, Kunstigalerii) katkenud liikumise motiiv toob kompositsioonilahendusse veidi traditsioonilisust. Hilised teosed (1794-1795, Dresden, kunstigalerii; 1808, Winterthur, Kunsthalle) loovad kuvandi kunstnikust, kelle looming tähistas paljusid olulisi 18. sajandi saksa kultuuri nähtusi, pannes paika järgneva sajandi realistliku kujundi traditsioone. IN hiline periood kunstnik maalis hulga maastikke, mis iseloomustavad tema suurepärast elust joonistamise oskust, pleenirhuvi ja “meeleolumaastiku” probleemi arengut (Vaade Dresdeni ümbrusele, 1800; Hommik, u 1800; Keskpäev, umbes 1800; Õhtu, umbes 1800, kõik - Dresden, kunstigalerii).

VLADIMIRI RIIKPEDAGOOGIAÜLIKOOL

ABSTRAKTNE

"GRAAFIDE TEOORIA"

Esitatud:

Zudina T.V.

Vladimir 2001

1. Sissejuhatus

2. Graafiteooria tekkelugu

3. Graafiteooria põhidefinitsioonid

4. Graafiteooria põhiteoreemid

5. Graafiteooria rakendamise ülesanded

6. Graafiteooria rakendamine kooli matemaatikakursusel

7. Graafiteooria rakendamine erinevates teaduse ja tehnika valdkondades

8. Hiljutised edusammud graafiteoorias

§1. GRAAFITEOORIA VÄLJUMISE AJALUGU.

Graafiteooria rajajaks peetakse matemaatik Leonhard Eulerit (1707-1783). Selle teooria ajalugu saab jälgida suure teadlase kirjavahetuse kaudu. Siin on ladinakeelse teksti tõlge, mis on võetud Euleri kirjast Itaalia matemaatikule ja insenerile Marinonile, mis saadeti Peterburist 13. märtsil 1736 [vt. lk 41–42]:

"Kunagi esitati mulle probleem Königsbergi linnas asuva saare kohta, mida ümbritseb jõgi, millest üle viskab seitse silda. Küsimus on selles, kas keegi saab neist pidevalt ümber sõita, läbides iga silla ainult korra. Ja siis ma olin teatas, et keegi pole siiani suutnud seda teha, kuid keegi pole ka tõestanud, et see on võimatu See küsimus, kuigi triviaalne, tundus mulle siiski tähelepanu vääriv, kuna ei geomeetria, algebra ega kombinatoorne kunst pole selle lahendamiseks piisav... Pärast pikka mõtlemist leidsin täiesti veenval tõendil põhineva lihtsa reegli, mille abil on võimalik kõikides sedalaadi probleemides kohe kindlaks teha, kas sellist ümbersõitu saab teha läbi mõne sildade arv, mis paiknevad mis tahes viisil või mitte, et neid saaks kujutada järgmisel joonisel[joon.1] , mille peal A tähistab saart ja B , C ja D - mandri osad, mis on üksteisest jõeharudega eraldatud. Seitse silda on tähistatud tähtedega a , b , c , d , e , f , g ".

(JOONIS 1.1)

Seoses meetoditega, mille ta avastas sedalaadi probleemide lahendamiseks, kirjutas Euler [vt. lk 102–104]:

"Sellel lahendusel on oma olemuselt ilmselt vähe pistmist matemaatikaga ja ma ei saa aru, miks peaks seda lahendust ootama pigem matemaatikult kui üheltki teiselt inimeselt, sest seda otsust toetab ainult arutluskäik ja seda pole Selle lahenduse leidmiseks tuleb kaasata kõik matemaatikale omased seadused. Niisiis, ma ei tea, kuidas selgub, et küsimusi, millel on matemaatikaga väga vähe pistmist, lahendavad tõenäolisemalt matemaatikud kui teised."

Kas siis on võimalik Königsbergi sildadest ümber sõita, läbides neist sildadest ainult üks kord? Vastuse leidmiseks jätkame Euleri kirjaga Marinonile:

"Küsimus seisneb selles, kas kõigist neist seitsmest sillast on võimalik mööda minna, läbides iga ühe korra või mitte. Minu reegel viib sellele küsimusele järgmise lahenduseni. Kõigepealt tuleb vaadata, kui palju alasid seal on. on veega eraldatud - sellised , millel pole muud üleminekut ühelt teisele peale silla. Selles näites on neli sellist sektsiooni - A , B , C , D . Järgmisena tuleb eristada, kas nendele üksikutele lõikudele viivate sildade arv on paaris või paaritu. Niisiis viib meie puhul viis silda A lõiguni ja kolm silda ülejäänuteni, st üksikute lõikudeni viivate sildade arv on veider ja sellest üksi piisab probleemi lahendamiseks. Kui see on kindlaks tehtud, rakendame järgmist reeglit: kui igale üksikule lõigule viivate sildade arv oleks paaris, siis oleks kõnealune ümbersõit võimalik ja samas oleks võimalik seda ümbersõitu alustada suvalisest lõigust. . Kui kaks neist arvudest oleksid paaritud, sest ainult üks ei saa olla paaritu, siis ka siis võiks üleminek toimuda, nagu ette nähtud, kuid kindlasti tuleb ühest kahest osast, kuhu paaritu arv viib, võtta ainult ahela algus. sillad. Kui lõpuks oleks rohkem kui kaks lõiku, kuhu viib paaritu arv sildu, siis on selline liikumine üldiselt võimatu ... kui siia saaks tuua muid, tõsisemaid probleeme, võib sellest meetodist veelgi rohkem kasu olla ja ei tohi tähelepanuta jätta."

Eeltoodud reegli põhjenduse võib leida L. Euleri sama aasta 3. aprilli kirjast oma sõbrale Ehlerile. Allpool jutustame uuesti väljavõtte sellest kirjast.

Matemaatik kirjutas, et üleminek on võimalik, kui jõe hargnemiskohas, kuhu viib paaritu arv sildu, pole rohkem kui kaks ala. Et seda oleks lihtsam ette kujutada, kustutame jooniselt juba läbitud sillad. Lihtne on kontrollida, et kui hakkame liikuma vastavalt Euleri reeglitele, ületame ühe silla ja kustutame selle, siis on joonisel lõik, kus jällegi pole rohkem kui kaks ala, kuhu viib paaritu arv sildu ja kui on paaritu arvu sildadega alad, kus me asume ühes neist. Niimoodi edasi liikudes läbime kõik sillad ühe korra.

Königsbergi linna sildade lool on tänapäevane jätk. Avame näiteks N.Ya toimetatud matemaatika kooliõpiku. Vilenkina kuuendasse klassi. Sellest leiame leheküljel 98 tähelepanelikkuse ja intelligentsuse arendamise pealkirja alt probleemi, mis on otseselt seotud sellega, mille Euler kunagi lahendas.

Ülesanne nr 569. Järvel on seitse saart, mis on omavahel ühendatud, nagu on näidatud joonisel 1.2. Millisele saarele peaks paat reisijaid viima, et nad saaksid ületada iga silla ja ainult ühe korra? Miks ei saa reisijaid saarele transportida? A ?

(JOONIS 1.2)

Lahendus. Kuna see ülesanne on sarnane Königsbergi sildade probleemiga, siis kasutame selle lahendamisel ka Euleri reeglit. Selle tulemusena saame järgmise vastuse: paat peab reisijad saarele toimetama E või F et nad saaksid iga silla korra ületada. Samast Euleri reeglist järeldub, et nõutav ümbersõit on võimatu, kui see algab saarelt A .

Kokkuvõtteks märgime, et Königsbergi sildade probleem ja sarnased probleemid koos nende uurimismeetodite kogumiga moodustavad praktilises mõttes väga olulise matemaatika haru, mida nimetatakse graafiteooriaks. Esimene töö graafikute kohta kuulus L. Eulerile ja ilmus 1736. aastal. Seejärel töötasid graafikute kallal Koenig (1774-1833), Hamilton (1805-1865) ja kaasaegsed matemaatikud C. Berge, O. Ore, A. Zykov.

§2. GRAAFITEOORIA PÕHITEOREEMID

Graafiteooria, nagu eespool mainitud, on matemaatikute jõupingutustega loodud matemaatiline distsipliin, mistõttu selle esitlus sisaldab vajalikke rangeid määratlusi. Niisiis, jätkame selle teooria põhimõistete organiseeritud sissejuhatusega.

Definitsioon 2.01. Count on piiratud arvu punktide kogum, mida nimetatakse tipud graafik ja paarisjooned, mis ühendavad mõnda neist tippudest, nn ribid või kaared graafik.

Seda määratlust saab sõnastada erinevalt: loendama nimetatakse mittetühjaks punktide komplektiks ( tipud) ja segmendid ( ribid), mille mõlemad otsad kuuluvad antud punktide hulka (vt joonis 2.1).

(JOONIS 2.1)

Järgnevalt tähistame graafi tippe ladina tähtedega A , B ,C ,D. Mõnikord tähistatakse graafikut tervikuna ühe suure tähega.

Definitsioon 2.02. Graafi tippe, mis ei kuulu ühtegi serva, nimetatakse isoleeritud .

Definitsioon 2.03. Graafi, mis koosneb ainult isoleeritud tippudest, nimetatakse null - loendama .

Määramine: O " – tippudega graaf, millel pole servi (joonis 2.2).

(JOONIS 2.2)

Definitsioon 2.04. Nimetatakse graafi, mille iga tippude paar on ühendatud servaga täielik .

Määramine: U " – graafik, mis koosneb n tipud ja servad, mis ühendavad nende tippude kõiki võimalikke paare. Sellist graafikut saab esitada kui n– kolmnurk, millesse on tõmmatud kõik diagonaalid (joonis 2.3).

(JOONIS 2.3)

Definitsioon 2.05. Kraad tipud on servade arv, kuhu tipp kuulub.

Määramine: lk (A) – tipu aste A . Näiteks joonisel 2.1: lk (A)=2, lk (B)=2, lk (C)=2, lk (D)=1, lk (E)=1.

Definitsioon 2.06. Loend, kõigi kraadid k mille tipud on identsed, nimetatakse homogeenne loendama kraadid k .

Joonistel 2.4 ja 2.5 on kujutatud teise ja kolmanda astme homogeensed graafikud.

(JOONIS 2.4 ja 2.5)

Definitsioon 2.07. Täiendus antud graafik on graaf, mis koosneb kõigist servadest ja nende otstest, mis tuleb täieliku graafiku saamiseks lisada algsele graafikule.

Joonis 2.6 näitab algset graafikut G , koosneb neljast tipust ja kolmest segmendist ning joonisel 2.7 - selle graafiku täiend - graaf G " .

(JOONIS 2.6 ja 2.7)

Näeme, et joonisel 2.5 on ribid A.C. Ja BD lõikuvad punktis, mis ei ole graafiku tipp. Kuid on juhtumeid, kui antud graafik tuleb tasapinnal esitada nii, et selle servad lõikuvad ainult tippudes (seda küsimust käsitletakse üksikasjalikumalt lõigus 5).

Definitsioon 2.08. Graafi, mida saab tasapinnal esitada nii, et selle servad lõikuvad ainult tippudes, nimetatakse tasane .

Näiteks joonisel 2.8 on kujutatud tasapinnaline graafik, mis on isomorfne (võrdne) joonisel 2.5 oleva graafikuga. Kuid pange tähele, et mitte iga graaf ei ole tasapinnaline, kuigi see on vastupidine, see tähendab, et iga tasapinnalist graafikut saab esitada tavalisel kujul.

(JOONIS 2.8)

Definitsioon 2.09. Kutsutakse tasapinnalise graafi hulknurka, mis ei sisalda graafi tippe ega servi serv .

2016 õppeaasta aasta

1. Sissejuhatus

2. Graafiteooria tekkelugu

3. Graafiteooria põhimõisted

4. Graafiteooria põhiteoreemid

5. Graafikute esitamise meetodid arvutis

6. Graafiteooria probleemide ülevaade

7. Järeldus

8. Viited

Sissejuhatus

Viimasel ajal on üha enam esile kerkinud teadusuuringud traditsiooniliselt diskreetse matemaatikaga seotud valdkondades. Koos selliste klassikaliste matemaatikaharudega nagu matemaatiline analüüs, diferentsiaalvõrrandid, V õppekava Erialal "Rakendusmatemaatika" ja paljudel teistel erialadel ilmusid sektsioonid matemaatilisest loogikast, algebrast, kombinatoorikast ja graafiteooriast. Selle põhjuseid ei ole raske mõista, lihtsalt tuvastades selle matemaatilise aparaadi põhjal lahendatud ülesannete ringi.

Graafiteooria tekkelugu.

1. Probleem Königsbergi sildadega. Joonisel fig. 1 on kujutatud Koenigsbergi linna (praegu Kaliningrad) keskosa skemaatiline plaan, mis sisaldab Pergola jõe kahte kallast, selles olevat kahte saart ja seitset ühendavat silda. Ülesanne on läbida kõik neli maaosa, ületades iga silla üks kord, ja naasta alguspunkti. Selle ülesande lahendas (näitati, et lahendust ei olnud) Euler 1736. aastal.

riis. 1

2. Kolme maja ja kolme kaevu probleem. Seal on kolm maja ja kolm kaevu, mis paiknevad kuidagi lennukis. Joonistage igast majast iga kaevu juurde tee, et teed ei ristuks (joonis 2). Selle probleemi lahendas (näitati, et lahendust pole) Kuratovski 1930. aastal.

riis. 2

3. Nelja värvi probleem. Tasapinna jagamist mittekattuvateks aladeks nimetatakse kaardiks. Kaardil olevaid alasid nimetatakse külgnevateks, kui neil on ühine piir. Ülesanne on värvida kaart nii, et kaks kõrvutiasetsevat ala ei oleks värvitud sama värviga (joonis 3). Üle-eelmise sajandi lõpust on olnud teada hüpotees, et selleks piisab neljast värvist. 1976. aastal avaldasid Appel ja Heiken neljavärviprobleemi lahenduse, mis põhines arvutiotsingul. Selle probleemi "programmiline" lahendamine oli pretsedent, mis tekitas tulise arutelu, mis pole sugugi lõppenud. Avaldatud lahenduse põhiolemus on katsetada suurt, kuid piiratud arvu (umbes 2000) tüüpi potentsiaalseid vastunäiteid neljavärviteoreemile ja näidata, et mitte ükski juhtum ei ole vastunäide. Selle otsingu lõpetas programm umbes tuhande superarvuti töötunniga. Saadud lahendust on võimatu "käsitsi" kontrollida - loenduse ulatus ületab palju inimvõimeid. Paljud matemaatikud tõstatavad küsimuse: kas sellist "programmitõestust" saab pidada kehtivaks tõendiks? Programmis võib ju vigu olla... Programmide õigsuse formaalse tõendamise meetodid ei ole rakendatavad sellise keerukusega programmide puhul, nagu käsitletav. Testimine ei garanteeri vigade puudumist ja sel juhul on see üldiselt võimatu. Seega jääb vaid loota autorite programmeerimisoskustele ja uskuda, et nad tegid kõik õigesti.

Riis. 3

Graafiteooria põhimõisted

1) Graafik G(V,E) on kahe hulga kogum – mittetühi hulk V (tippude hulk) ja hulga V kaheelemendiliste alamhulkade hulk E (E – servade hulk).

2) Orienteeritud on graaf, milles on järjestatud tipupaaride kogum kujul (x,y), kus x nimetatakse kaare alguseks ja y on kaare lõpp. Kaar (x, y) kirjutatakse sageli kui . Nad ütlevad ka, et kaar viib tipust x tippu y ja tippu y külgnevad tipuga x.

3) Kui hulga E element võib olla paar identsed V (mitte eristatavad) elemendid, siis nimetatakse hulga E sellist elementi silmus, ja graafikut nimetatakse graafik silmustega(või pseudograaf).

4) Kui E ei ole hulk, vaid seatud mis sisaldavad mitut identset elementi, siis nimetatakse neid elemente mitu serva, ja graafikut nimetatakse multigraaf.

5) Kui hulga E elemendid ei pruugi olla kaheelemendilised, vaid hulga V suvalised alamhulgad, siis nimetatakse selliseid hulga E elemente. hüperkaared, ja graafikut nimetatakse hüpergraaf.

6) Kui funktsioon on määratud F: V → M ja/või F: E → M, siis komplekt M nimetatakse komplektiks märkmeid, ja graafikut nimetatakse märgitud(või laetud). Märkide komplekt on tavaliselt tähed või täisarvud. Kui funktsioon F on injektiivne, st erinevatel tippudel (servadel) on erinevad sildid, siis kutsutakse graafikut nummerdatud.

7) Alamgraafik nimetatakse graafikuks G′(V′,E′), kus ja/või .

a) Kui V′ = V, siis kutsutakse G′ tuum alamgraaf G.

b) Kui , siis kutsutakse graafikut G′ oma Graafi G alamgraaf.

c) Alamgraafi G′(V′,E′) nimetatakse graafi G(V,E) regulaarseks alamgraafiks, kui G′ sisaldab G kõiki võimalikke servi.

8) Kraad (valents) tipud on sellele tipule langevate servade arv (sellega külgnevate tippude arv).

9) Tee graafis on vahelduv tippude ja servade jada, milles kaks külgnevat elementi langevad.

a) Kui , siis marsruut suletud, muidu avatud.

b) Kui kõik servad on erinevad, siis kutsutakse marsruuti kett.

c) Kui kõik tipud (ja seega ka servad) on erinevad, siis kutsutakse marsruuti lihtne kett.

d) nimetatakse suletud ahelat tsükkel.

e) Nimetatakse suletud lihtahelat lihtne silmus.

f) Nimetatakse tsükliteta graafik atsükliline.

g) Digraafide puhul nimetatakse ahelat kõrval, ja tsükkel on kontuur.

riis. 4. Marsruudid, ketid, tsiklid

Näide

Graafikul, mille skeem on näidatud joonisel 4:

1. v 1, v 3, v 1, v 4 – marsruut, kuid mitte kett;

2. v 1, v 3, v 5, v 2, v 3, v 4 – kett, kuid mitte lihtahel;

3. v 1, v 4, v 3, v 2, v 5 – lihtahel;

4. v 1, v 3, v 5, v 2, v 3, v 4, v 1 – tsükkel, kuid mitte lihttsükkel;

5. v 1 , v 3 , v 4 , v 1 – lihtne tsükkel.

10) Kui graafil on tsükkel (mitte tingimata lihtne), mis sisaldab ühekordselt kõiki graafi servi, siis sellist tsüklit nimetatakse Eulerian tsükkel.

11) Kui graafil on lihtne tsükkel, mis sisaldab kõiki graafi tippe (ükshaaval), siis sellist tsüklit nimetatakse Hamiltoni tsükkel.

12) puu nimetatakse ühendatud graafikuks ilma tsükliteta.

13) skelett Kutsutakse puud, mis sisaldab kõiki graafi tippe.

14) Sobivus on servade kogum, milles ei ole kahte kõrvuti.

15) Sobivus kutsutakse maksimaalselt, kui ükski selle superhulk pole sõltumatu.

16) Graafi kaks tippu ühendatud, kui neid ühendab lihtne kett.

17) Graafi, mille kõik tipud on ühendatud, nimetatakse sidus.

18) Graafi, mis koosneb ainult isoleeritud tippudest, kutsutakse üsna ebaühtlane.

19) Marsruudi pikkus nimetatakse selles olevate servade arvu (koos kordustega).

20) Kaugus tippude u ja v vahelist kohta nimetatakse lühima ahela pikkuseks ja lühimat ahelat ennast geodeetiline.

21) Läbimõõt graafiku G pikkust nimetatakse pikima geodeetiliseks pikkuseks.

22) Ekstsentrilisus tipp v ühendatud graafis G(V,E) on maksimaalne kaugus tipust v graafi G teiste tippudeni.

23) Raadius Graafi G nimetatakse tippude ekstsentrilisusest väikseimaks.

24) Tipp v nimetatakse keskne, kui selle ekstsentrilisus langeb kokku graafiku raadiusega.

25) Kesktippude hulka kutsutakse Keskus graafik.

riis. 5 Graafikute tippude ja keskpunktide ekstsentrilisused (esile tõstetud).

Seotud Informatsioon.

Materjal Wikipediast – vabast entsüklopeediast

Graafiteooria- diskreetse matemaatika haru, mis uurib graafikute omadusi. Üldises mõttes on graafik kujutatud hulgana tipud(sõlmed) ühendatud ribid. Ranges määratluses nimetatakse sellist hulkade paari graafiks. $G\; =\; (V,\; E)$, Kus $V$ on mis tahes loendatava hulga alamhulk ja $E$- alamhulk $V\backslash \; korda\; V$.

Graafiteooria leiab rakendust näiteks geograafilistes infosüsteemides (GIS). Tippudena käsitletakse olemasolevaid või äsja projekteeritud maju, rajatisi, plokke jms ning servadena neid ühendavaid teid, tehnovõrke, elektriliine jms. Erinevate sellisel graafikul tehtavate arvutuste kasutamine võimaldab näiteks leida lühima ümbersõidutee või lähima toidupoe või planeerida optimaalse marsruudi.

Graafiteooria sisaldab suur hulk lahendamata probleemid ja seni tõestamata hüpoteesid.

Graafiteooria ajalugu

Leonard Eulerit peetakse graafiteooria rajajaks. 1736. aastal sõnastas ta ühes oma kirjas ja pakkus välja lahenduse Königsbergi seitsme silla probleemile, millest sai hiljem üks graafiteooria klassikalisi probleeme.

Graafiteooria terminoloogia

Graafikute kujutamine tasapinnal

Kõige sagedamini kasutatakse seda graafikute kujutamisel piltidel järgmine süsteem tähistused: graafiku tipud on kujutatud punktidega või tipu tähenduse täpsustamisel ristkülikute, ovaalidega vms, kus tipu tähendus selgub joonise sees (algoritmide vooskeemide graafikud). Kui tippude vahel on serv, siis on vastavad punktid (kujundid) ühendatud sirge või kaarega. Suunatud graafi puhul asendatakse kaared nooltega või on selgelt näidatud serva suund. Mõnikord asetatakse serva kõrvale selgitavad pealdised, mis paljastavad serva tähenduse, näiteks lõplike olekumasinate üleminekugraafikutes. Seal on tasapinnalised ja mittetasapinnalised graafikud. Tasapinnaline graaf on graaf, mida saab pildil (tasapinnal) kujutada ilma lõikuvate servadeta (lihtsamad on kolmnurk või ühendatud tippude paar), vastasel juhul on graaf mittetasapind. Juhul, kui graafik ei sisalda tsükleid (mis sisaldab vähemalt ühte teed üks kord servade ja tippude läbimine algse tipu juurde tagasipöördumisega), nimetatakse seda tavaliselt "puuks". Graafiteoorias on olulised puuliigid binaarsed puud, kus igal tipul on üks sissetulev serv ja täpselt kaks väljaminevat serva või on see lõplik – sellel pole väljuvaid servi ja see sisaldab ühte juurtippu, millel puudub sissetulev serv.

Graafiku pilti ei tohi segi ajada graafi endaga (abstraktne struktuur), kuna ühe graafikuga võib seostada rohkem kui ühe graafilise esituse. Pilt on mõeldud ainult selleks, et näidata, millised tipupaarid on servadega ühendatud ja millised mitte. Tihti on praktikas keeruline vastata küsimusele, kas kaks pilti on sama graafiku mudelid või mitte (ehk kas piltidele vastavad graafikud on isomorfsed). Olenevalt ülesandest võivad mõned pildid pakkuda rohkem selgust kui teised.

Mõned graafiteooria probleemid

• Königsbergi seitse silda on üks esimesi tulemusi graafiteoorias, mille Euler avaldas aastal.
• Nelja värvi probleem sõnastati 1852. aastal, kuid mitteklassikaline tõestus saadi alles 1976. aastal (keral (tasapinnal) oleva kaardi jaoks piisab 4 värvist).
• Rändmüüja probleem on üks kuulsamaid NP-ga seotud probleeme.
• Klikiprobleem on veel üks NP-täielik probleem.
• Minimaalse ulatuva puu leidmine.
• Graafi isomorfism – kas ühe graafi tippe ümber nummerdades on võimalik saada teist?
• Graafiku tasapinnalisus - kas graafikut on võimalik kujutada tasapinnal ilma servade lõikepunktideta (või minimaalse kihtide arvuga, mida kasutatakse trükkplaatide või mikroskeemide elementide omavaheliste ühenduste jälgimisel).

Graafiteooria rakendamine

Vaata ka

Kirjutage ülevaade artiklist "Graafiteooria"

Märkmed

Kirjandus

• Distel R. Graafiteooria Trans. inglise keelest - Novosibirsk: Matemaatika Instituudi kirjastus, 2002. - 336 lk. ISBN 5-86134-101-X.
• Diestel R.. - NY: Springer-Verlag, 2005. - Lk 422.
• Basaker R., Saati T.
• Belov V.V., Vorobjev E.M., Šatalov V.E. Graafiteooria. - M.: Kõrgem. kool, 1976. - Lk 392.
• Berge K.
• Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tõškevitš R. I. Graafiteooria loengud. M.: Nauka, 1990. 384 lk. (Toim. 2, muudetud M.: URSS, 2009. 392 lk.)
• Zykov A.A.. - M.: “Ülikooliraamat”, 2004. - Lk 664. - ISBN 5-9502-0057-8.(M.: Nauka, 1987. 383c.)
• Topoloogia ja graafiteooria keemilised rakendused. Ed. R. King. Per. inglise keelest M.: Mir, 1987.
• Kirsanov M. N. Graafikud Maple'is. M.: Fizmatlit, 2007. 168 lk. vuz.expponenta.ru/PDF/book/GrMaple.pdf eqworld.ipmnet.ru/ru/library/books/Kirsanov2007ru.pdf
• Christofides N.
• Cormen T.H. et al. VI osa. Algoritmid graafikutega töötamiseks // Algoritmid: konstrueerimine ja analüüs = Algoritmide sissejuhatus. - 2. väljaanne - M.: Williams, 2006. - Lk 1296. - ISBN 0-07-013151-1.
• Maagi O.. - 2. väljaanne - M.: Teadus, 1980. - Lk 336.
• Salii V. N. Bogomolov A. M.. - M.: Füüsika ja matemaatika kirjandus, 1997. - ISBN 5-02-015033-9.
• Swami M., Thulasiraman K.
• Tutt W.
• Wilson R.
• Harari F.. - M.: Mir, 1973.(Toim. 3, M.: KomKniga, 2006. - 296 lk)
• Harari F., Palmer E.. - Maailm, 1977.
• Sergei Melnikov// Teadus ja elu . - 1996. - Väljaanne. 3. - lk 144-145. Artikkel räägib Gustav Simmonsi leiutatud graafikumängust Sim.

Lingid

• : programm, mis pakub kasutajale laia valikut tööriistu ja meetodeid teabe visualiseerimiseks ja graafikutest otsimiseks

Klassikaline analüüs Funktsiooniteooria Diferentsiaal- ja integraalvõrrandid

Graafiteooriat iseloomustav väljavõte

Kuid enne, kui ta need sõnad lõpetas, hüppas prints Andrei, tundes häbi- ja vihapisaraid kurku tõusmas, juba hobuse seljast ja jooksis lipu juurde.
- Poisid, jätkake! – hüüdis ta lapselikult.
"Siin see on!" mõtles prints Andrei, haarates lipuvardast ja kuuldes mõnuga kuulide vilet, mis oli ilmselgelt konkreetselt tema pihta suunatud. Mitmed sõdurid langesid.
- Hurraa! - hüüdis prints Andrei, hoides vaevu rasket lipukirja käes, ja jooksis edasi kahtlemata enesekindlalt, et kogu pataljon jookseb talle järele.
Tõepoolest, ta jooksis üksi vaid mõne sammu. Üks sõdur asus teele, siis teine ​​ja kogu pataljon hüüdis "Hurraa!" jooksis ette ja möödus temast. Pataljoni allohvitser jooksis üles ja võttis vürst Andrei käest raskusest värisenud lipukirja, kuid sai kohe surma. Prints Andrei haaras uuesti lipukirjast ja põgenes seda vardast vedades koos pataljoniga. Tema ees nägi ta meie suurtükiväelasi, kellest osa võitles, teised hülgasid kahurid ja jooksid tema poole; ta nägi ka prantsuse jalaväesõdureid, kes haarasid suurtükiväehobuseid ja pöörasid püssi. Prints Andrei ja tema pataljon olid relvadest juba 20 sammu kaugusel. Ta kuulis enda kohal lakkamatut kuulide vilinat ning sõdurid oigasid pidevalt ning langesid temast paremale ja vasakule. Aga ta ei vaadanud neid; ta piilus ainult seda, mis tema ees toimus – aku peal. Ta nägi selgelt ühte punajuukselist suurtükiväelast, kelle ühel küljel oli koputatud shako, mis tõmbas ühel küljel lipukirja, samal ajal kui prantsuse sõdur tõmbas teisel pool plakatit enda poole. Prints Andrey nägi juba selgelt nende kahe inimese näos segaduses ja samal ajal kibestunud ilmet, kes ilmselt ei saanud aru, mida nad teevad.
"Mida nad teevad? - mõtles prints Andrei neile otsa vaadates: - miks punajuukseline suurtükiväelane ei jookse, kui tal pole relvi? Miks prantslane teda noaga ei löö? Enne kui ta temani jõuab, mäletab prantslane relva ja pussitab ta surnuks.
Tõepoolest, üks teine ​​prantslane, relv käes, jooksis võitlejate juurde ja otsustada tuli punajuukselise suurtükiväelase saatus, kes ikka veel ei mõistnud, mis teda ees ootab ja võidukalt lipu välja tõmbas. Kuid prints Andrei ei näinud, kuidas see lõppes. Talle tundus, et üks lähedalasuvatest sõduritest lõi talle otsekui tugevat pulka õõtsudes pähe. Natuke valutas ja mis kõige tähtsam, see oli ebameeldiv, sest see valu pakkus talle meelelahutust ja takistas nägemast seda, mida ta vaatas.
"Mis see on? Ma kukun? Mu jalad annavad järele,” mõtles ta ja kukkus selili. Ta avas silmad, lootes näha, kuidas prantslaste ja suurtükiväelaste võitlus lõppes, ning tahtes teada, kas punajuukseline suurtükiväelane sai surma või mitte, kas relvad võeti ära või päästeti. Aga ta ei näinud midagi. Tema kohal polnud enam midagi peale taeva - kõrge taevas, mitte selge, kuid siiski mõõtmatult kõrge, hallid pilved vaikselt mööda seda hiilivad. "Kui vaikne, rahulik ja pühalik, üldse mitte nii nagu mina jooksin," mõtles prints Andrei, "mitte nagu see, kuidas me jooksime, karjusime ja võitlesime; See pole sugugi niisugune, kuidas prantslane ja suurtükiväelane kibestunud ja hirmunud nägudega teineteise plakateid tõmbasid – sugugi mitte nagu see, kuidas pilved üle selle kõrge lõputu taeva roomavad. Miks ma pole seda kõrget taevast varem näinud? Ja kui õnnelik ma olen, et ma ta lõpuks ära tundsin. Jah! kõik on tühi, kõik on pettus, välja arvatud see lõputu taevas. Pole midagi, mitte midagi peale tema. Aga sedagi pole, pole muud kui vaikus, rahu. Ja jumal tänatud! ”…

Bagrationi paremal tiival kell 9 polnud äri veel alanud. Tahtmata nõustuda Dolgorukovi nõudega äri alustada ja tahtes vastutust endalt kõrvale juhtida, soovitas vürst Bagration saata Dolgorukov selle ülemjuhatajalt küsima. Bagration teadis, et kui saadetut ei tapetud (mis oli väga tõenäoline), ja isegi kui ta leiab ülemjuhataja, mis oli väga raske, teadis Bagration peaaegu 10 versta kauguse tõttu, mis eraldab ühte tiiba teisest, saadetul poleks varem õhtuti aega tagasi tulla.
Bagration vaatas oma suurte, ilmetute, unetud silmadega ringi oma saatjaskonnas ja esimesena torkas talle silma Rostovi lapselik nägu, mis oli tahtmatult tardunud põnevusest ja lootusest. Ta saatis selle.
- Mis siis, kui kohtun Tema Majesteediga enne ülemjuhatajat, Teie Ekstsellents? - ütles Rostov, hoides kätt visiiri küljes.
"Võite selle oma Majesteedile üle anda," ütles Dolgorukov Bagrationi kiirustades katkestades.
Keti alt vabanenuna suutis Rostov enne hommikut mitu tundi magada ja tundis end rõõmsameelse, julge, otsustusvõimelisena, selle liigutuste elastsusega, enesekindlusega oma õnne ja selle meeleoluga, milles kõik tundub lihtne, lõbus ja võimalik.
Kõik tema soovid täitusid sel hommikul; peeti üldlahing, ta võttis sellest osa; Pealegi oli ta julgema kindrali alluvuses korrapidaja; Veelgi enam, ta sõitis tööülesannetega Kutuzovi ja võib-olla isegi suverääni enda juurde. Hommik oli selge, hobune tema all oli hea. Tema hing oli rõõmus ja õnnelik. Saanud käsu, pani ta hobuse teele ja kihutas mööda joont. Algul ratsutas ta mööda Bagrationi vägede rida, mis polnud veel tegevusse astunud ja seisis liikumatult; siis sisenes ta Uvarovi ratsaväe poolt hõivatud ruumi ja märkas siin juba liigutusi ja märke juhtumi ettevalmistamisest; Möödunud Uvarovi ratsaväest, kuulis ta juba selgelt enda ees kahuri- ja püssipauku. Tulistamine tugevnes.
Värskes hommikuõhus ei kostnud enam, nagu varem, ebaregulaarsete ajavahemike järel kaks, kolm lasku ja siis üks-kaks püssilasku ning mägede nõlvadel Pratzeni ees kostis tulistamist, katkestati. nii sagedaste püssipaugudega, et mõnikord ei eraldunud mitu kahurilasku enam üksteisest, vaid sulandusid üheks ühiseks mürinaks.
Oli näha, kuidas püsside suits näis jooksvat mööda nõlvu, jõudes üksteisele järele, ja kuidas püsside suits keerles, ähmastus ja sulandus üksteisega. Suitsu vahelt tääkide särast paistsid liikuvad jalaväemassid ja kitsad roheliste kastidega suurtükiribad.
Rostov peatas oma hobuse minutiks künkal, et uurida, mis toimub; kuid ükskõik kui kõvasti ta oma tähelepanu ka ei pingutanud, ei saanud ta toimuvast midagi aru ega aru saada: osa inimesi liikus seal suitsu sees, mõned vägede lõuendid liikusid nii ees kui taga; aga miks? WHO? Kuhu? sellest oli võimatu aru saada. See vaatepilt ja need helid mitte ainult ei tekitanud temas mingit nüri ega arglikku tunnet, vaid, vastupidi, andsid energiat ja sihikindlust.
"Noh, rohkem, anna veel!" - Ta pöördus vaimselt nende helide poole ja hakkas uuesti mööda joont galoppima, tungides üha kaugemale juba tegutsenud vägede piirkonda.
"Ma ei tea, kuidas seal läheb, aga kõik saab korda!" mõtles Rostov.
Möödunud mõnest Austria väest, märkas Rostov, et rivi järgmine osa (see oli valvur) oli juba tegutsenud.
"Seda parem! Vaatan lähemalt,” arvas ta.
Ta sõitis peaaegu mööda rindejoont. Tema poole kihutas mitu ratsanikku. Need olid meie päästjad, kes naasid rünnakult korratutes ridades. Rostov möödus neist, märkas tahes-tahtmata üht neist verine ja kihutas edasi.
"Ma ei hooli sellest!" ta mõtles. Enne kui ta oli pärast seda paarsada sammu ratsutanud, ilmus temast vasakule kogu väljaku pikkuses tohutu mass läikivvalgetes mundrites mustadel hobustel ratsaväelasi, kes traavisid otse tema poole. Rostov pani oma hobuse täis galopi, et nende ratsaväelaste eest ära saada ja ta oleks neist eemale pääsenud, kui nad oleksid sama kõnnaku hoidnud, kuid nad muudkui kiirendasid, nii et mõned hobused juba kappasid. Rostov kuulis üha selgemalt nende trampimist ja relvade kõlinat ning nende hobused, figuurid ja isegi näod muutusid paremini nähtavaks. Need olid meie ratsaväelased, kes läksid rünnakule Prantsuse ratsaväele, mis nende poole liikus.
Ratsavalvurid galoppisid, kuid hoidsid endiselt oma hobuseid. Rostov nägi juba nende nägusid ja kuulis käsku: "marss, marss!" lausus ohvitser, kes lasi oma verehobuse täiskiirusel valla. Rostov, kartes purustamist või prantslaste rünnakule meelitamist, kihutas hobune mööda rinnet nii kiiresti kui suutis, ega õnnestunud ikkagi neist mööda saada.
Viimane ratsaväevalvur, hiiglaslik täkiline mees, kortsutas vihaselt kulmu, nähes enda ees Rostovit, kellega ta paratamatult kokku põrkaks. See ratsavaht oleks kindlasti Rostovi ja tema beduiini maha löönud (Rostov ise tundus nende hiigelsuurte inimeste ja hobustega võrreldes nii väike ja nõrk), kui ta poleks mõelnud oma piitsaga ratsaväevahi hobusele silma visata. Must, raske, viietolline hobune hiilis eemale, pani kõrvad pikali; kuid täkkega ratsaväevalvur torkas tema külgedele tohutuid kannused ning hobune saba lehvitades ja kaela sirutades tormas veelgi kiiremini. Niipea kui ratsaväelased Rostovist möödusid, kuulis ta neid hüüdmas: "Hurraa!" ja tagasi vaadates nägi ta, et nende esiread segunesid võõraste, arvatavasti prantslaste, punastes epaulettides ratsaväelastega. Kaugemale polnud võimalik midagi näha, sest kohe pärast seda hakkasid kuskilt paukuma kahurid ja kõik oli kaetud suitsuga.
Sel hetkel, kui temast möödunud ratsaväelased suitsu kadusid, kõhkles Rostov, kas galoppida neile järele või minna sinna, kuhu vaja. See oli ratsaväekaitsjate hiilgav rünnak, mis üllatas prantslasi endid. Rostov kartis hiljem kuulda, et kogu sellest tohututest ilusatest inimestest, kõigist hiilgavatest, rikastest noortest tuhandetel hobustel, ohvitseridest ja kadettidest, kes temast mööda kihutasid, jäi pärast rünnakut alles vaid kaheksateist inimest.