Täiesti lahti ühendatud graafikud . Graafi, mille paljud servad on tühjad, nimetatakse üsna ebaühtlane(või tühi) graafik. Täiesti lahtiühendatud n tipuga graafi tähistame N n ; N4 on näidatud joonisel fig. 1. Pange tähele juures Täielikult lahtiühendatud graafi kõik tipud on isoleeritud. Täiesti lahti ühendatud graafikud ei paku erilist huvi.

Täielikud graafikud . Nimetatakse lihtsat graafikut, mille suvalised kaks tippu on kõrvuti täielik graafik. Täielikku n tipuga graafikut tähistatakse tavaliselt tähisega. Graafikud ja on näidatud joonisel fig. 2 ja 3. omab täpselt n (n - 1)/2 serva.

Regulaarsed graafikud . Kutsutakse graafikut, mille kõigil tippudel on sama aste tavaline graafik. Kui iga tipu aste on r, siis kutsutakse graafikut regulaarne kraad r. 3. astme regulaargraafikud, mida nimetatakse ka kuupmeetrit(või kolmevalentne) graafikud (vt näiteks joon. 2 ja 4). Teine kuulus kuupgraafiku näide on nn krahv Petersen, näidatud joonisel fig. 5. Pange tähele, et iga täielikult lahtiühendatud graaf on korrapärane astmega 0 ja iga täielik graaf K n on korrapärane astmega n - 1.

Platoonilised graafikud . Regulaarsetest graafikutest on eriti huvitavad nn platoonilised graafikud - viie korrapärase hulktahuka tippudest ja servadest moodustunud graafid - platoonilised tahkised: tetraeedr, kuup, oktaeedr, dodekaeedr ja ikosaeedr. Graafik vastab tetraeedrile (joonis 2); kuubile ja oktaeedrile vastavad graafikud on näidatud joonisel fig. 5 ja 6;

Kahepoolsed graafikud . Oletame, et graafi tippude hulga saab jagada kaheks disjunktseks alamhulgaks V 1 ja V 2 nii, et iga serv G-s ühendab mõne tipu V 1-st mõne tipuga V 2 (joonis 7);

siis G-d nimetatakse kahepoolseks graafikuks. Selliseid graafikuid nimetatakse mõnikord G(V 1, V 2), kui tahetakse eristada kahte määratud alamhulka. Kahepoolset graafi saab defineerida ka muul viisil - selle tippude värvimise osas kahe värviga, näiteks punase ja sinisega. Graafi nimetatakse kahepoolseks, kui iga selle tippu saab värvida punaseks või siniseks nii, et iga serva üks ots on punane ja teine sinine. Tuleb rõhutada, et kahepoolses graafis ei ole vaja, et iga V 1 tipp oleks ühendatud iga V 2 tipuga; kui see on nii ja kui graaf G on lihtne, siis seda nimetatakse täielik kahepoolne graafik ja on tavaliselt tähistatud kus m, n on vastavalt V 1 ja V 2 tippude arv. Näiteks joonisel fig. 8 näitab graafikut K 4, 3. Pange tähele, et graafil on täpselt m + n tippu ja mn serva. Vormi täielikku kahepoolset graafikut nimetatakse tähtgraafikuks; joonisel fig. 9 näitab tähtgraafikut.

Ühendatud graafikud . Graafik ühendatud, kui seda ei saa esitada kahe graafiku ühendusena ja ebaühtlane muidu. Ilmselgelt saab iga lahtiühendatud graafi G esitada lõpliku arvu ühendatud graafide liiduna – iga sellist ühendatud graafikut nimetatakse komponent (ühenduvus) graafik G. (Joonis 10 kujutab kolme komponendiga graafikut.) Tihti on suvaliste graafikute puhul mugav teatud väiteid esmalt tõestada ühendatud graafikute puhul ja seejärel rakendada neid iga komponendi puhul eraldi.

Graafiku diagrammi, mis koosneb "eraldatud" tippudest, nimetatakse null graafik. (Joonis 2)

Kutsutakse graafikuid, millel pole konstrueeritud kõiki võimalikke servi mittetäielikud graafikud. (Joonis 3)

Kutsutakse graafikuid, millel on konstrueeritud kõik võimalikud servad täielikud graafikud. (Joonis 4)

Kui graafi servadel on nooled, mis näitavad servade suunda, siis sellist graafikut nimetatakse suunatud.

Joonisel näidatud graafikul olev nool ühelt töölt teisele tähendab tööde järjestust.

Seinte paigaldamisega ei saa alustada ilma vundamenti ehitamata, viimistluse alustamiseks peab põrandatel olema vesi jne.

Tippude astmed ja servade arvu arvestamine.

Graafi tipust väljuvate servade arvu nimetatakse tipu astmeks. Graafi tippu, millel on paaritu aste, nimetatakse paarituks ja tippu, millel on paaris aste, nimetatakse paarituks.

Kui graafi kõigi tippude astmed on võrdsed, siis kutsutakse graafi homogeenne. Seega on iga täielik graafik homogeenne.

Joonisel 5 on kujutatud viie tipuga graafik.

Tipu A aste tähistatakse tähega St.A.

Pildil:
St.A = 1, St.B = 2, St.B = 3, St.G = 2, St.D = 0.

Sõnastagem mõned teatud graafikutele omased seaduspärasused.

Muster 1. Tervikgraafiku tippude astmed on samad ja igaüks neist on 1 võrra väiksem selle graafi tippude arvust.

Muster 2. Graafi tippude astmete summa on paarisarv, mis võrdub kahekordse graafi servade arvuga.

See muster kehtib mitte ainult terve graafiku, vaid ka mis tahes graafiku kohta.

Iga graafi paaritute tippude arv on paaris.

Pange tähele, et kui tervel graafil on n tippu, siis on servade arv võrdne n(n-1)/2.

Mittetäieliku graafiku saab täiendada samade tippudega, lisades puuduvad servad. Näiteks joonisel 3 on kujutatud mittetäielik viie tipuga graafik. Joonisel 4 on servad, mis muudavad graafi terviklikuks graafiks, kujutatud erineva värviga, nende servadega graafi tippude kogumit nimetatakse graafi komplemendiks.

Euleri graafikud.

Nimetatakse graafik, mille saab joonistada pliiatsit paberilt tõstmata Eulerian. (Joon.6)

Need graafikud on nime saanud teadlase järgi Leonhard Euler.

Muster 3.(tuleneb meie käsitletud teoreemist).
Paaritu arvu paaritute tippudega graafikut on võimatu joonistada.

Muster 4. Kui kõik graafiku tipud on paaris, saate seda graafikut joonistada ilma pliiatsit paberilt tõstmata (“ühe tõmbega”), liikudes mööda iga serva ainult üks kord. Liikumine võib alata mis tahes tipust ja lõppeda samas tipus.

Muster 5. Ainult kahe paaritu tipuga graafikut saab joonistada ilma pliiatsit paberilt tõstmata ning liikumine peab algama ühest neist paaritutest tippudest ja lõppema neist teisest.

Muster 6. Rohkem kui kahe paaritu tipuga graafikut ei saa joonistada " ühe tõmbega».

Nimetatakse joonist (graafikut), mille saab joonistada pliiatsit paberilt tõstmata ühetähenduslik.

Graafikut nimetatakse sidus, kui selle mis tahes kahte tippu saab ühendada teega, st servade jadaga, millest igaüks algab eelmise lõpust.

Joonis 7 näitab ilmselgelt lahtiühendatud graafikut.

Graafikut nimetatakse ebaühtlane, kui see tingimus ei ole täidetud.

Kui näiteks joonisel joonistada tippude D ja E vahele serv, siis muutub graaf ühendatud.( Joonis 8)

Graafiteoorias nimetatakse sellist serva (mille eemaldamise järel muutub graaf ühendatud küljest lahtiühendatuks) nn. sild.

Sildade näited peal Joonis 7 teenida võiksid servad DE, A3, VZh jne, millest igaüks ühendaks graafi “eraldatud” osade tipud. ( Joonis 8)

Lahti ühendatud graafik koosneb mitmest " tükid" Neid "tükke" nimetatakse graafiku ühendatud komponentideks. Iga ühendatud komponent on loomulikult ühendatud graafik. Pange tähele, et ühendatud graafikul on üks ühendatud komponent.

Graaf on Euleri siis ja ainult siis, kui see on ühendatud ja sellel on maksimaalselt kaks paaritut tippu.

puud.

puu Kutsutakse iga ühendatud graafikut, millel pole tsükleid.

Tsükkel on tee, mille algus ja lõpp langevad kokku.

Kui tsükli kõik tipud on erinevad, siis sellist tsüklit nimetatakse elementaarne(või lihtne) tsükkel.

Kui tsükkel sisaldab ühe korra kõiki graafiku servi, siis nimetatakse sellist tsüklit Euleri joon (Joonis 9a).

Veerus sees Joonis 9b kaks tsüklit: 1-2-3-4-1 ja 5-6-7-5.

Kõrval graafis ühest tipust teise on servade jada, mida mööda saab nende tippude vahele rajada marsruudi.

Sel juhul ei tohiks ükski marsruudi serv ilmuda rohkem kui üks kord. Nimetatakse tippu, millest marsruut rajatakse teekonna algus, tipp marsruudi lõpus - tee lõpp.

rippuv top on tipp, millest väljub täpselt üks serv ( Joonis 10).
(rippuvad tipud on ringiga).

Iga puutippude paari jaoks on ainulaadne tee, mis neid ühendab.

Seda omadust kasutatakse kõigi esivanemate leidmisel sugupuust, näiteks meessoost sugupuust iga inimese, kelle sugupuu on esindatud sugupuu kujul, mis on " puu"ja graafiteooria mõttes.

Iga puu serv on sild.

Tõepoolest, pärast puu mis tahes serva eemaldamist, see " laguneb laiali"kahe puu peal.

Graaf, mille mis tahes kaks tippu on ühendatud täpselt ühe lihtsa teega, on puu.

(rippuva topi kohta). Igal puul on rippuv latv.

. Puu tippude arv on ühe võrra suurem kui servade arv.

Isomorfism. Tasapinnalised graafikud ja Euleri teoreem.

Neid kahte graafikut nimetatakse isomorfne, kui neil on võrdne arv tippe ja iga graafi tippe saab nummerdada vahemikus 1 kuni n, nii et esimese graafi tipud on ühendatud servaga siis ja ainult siis, kui teise graafi vastavad tipud on ühendatud serv.

Tõestame, et joonisel 11 kujutatud graafikud on isomorfsed.

Nummerdame esimese ja teise graafiku tipud 1 kuni 4 ( Joonis 12).

Esimene graaf ühendab tipud 1 ja 2, 2 ja 3, 3 ja 4, 1 ja 4, 1 ja 3, 2 ja 4; Pange tähele, et teises graafi tipud 1 ja 2, 2 ja 3, 3 ja 4, 1 ja 4, 1 ja 3, 2 ja 4 on samuti ühendatud, seetõttu on need graafikud isomorfsed.

Selleks et teada saada, kas kaks graafikut on isomorfsed, peate veenduma, et neil on:

sama arv tippe
kui ühe graafi tipud on ühendatud servaga, siis teise graafi vastavad tipud on samuti servaga ühendatud.

Nimetatakse graafikut, mille saab koostada nii, et selle servad ei lõiku kusagil mujal, välja arvatud selle tippudes tasane või tasapinnaline.

Euler. Korrektselt koostatud tasapinnalise graafi jaoks on sellel võrdus: V-E+F=2, kus V on tippude arv, E on servade arv, F on tükkide arv. (Võrdsus V -E+ F=2 nimetatakse tavaliselt Euleri valemiks).

Nimetatakse graafi, mille iga tipp on ühendatud iga teise tipu servaga täielik.

Pontrjagin – Kuratovski. Graaf on tasane siis ja ainult siis, kui see ei sisalda (topoloogilises mõttes) kuue tipuga “maja-kaev” tüüpi graafi ja viie tipuga terviklikku graafi.

(Kasutatakse peamiselt iidsetes majade ja kaevude probleemides, mille olemus taandub küsimuse selgitamisele - kas kõnealune graafik on tasane või mitte, Joonis 13)

Suunatud graafikud.

On olulisi praktiliste probleemide klasse, mida ei saa eelnevalt käsitletud graafikutüüpide abil lahendada.

Näiteks linna teede ja väljakute kaart on kujutatud tasapinnalise graafiku abil. Aga kui teil on vaja seda skeemi kasutada autoga linnas ringi sõitmiseks ja liiklus on mõnel (või kõigil) tänavatel ühesuunaline?

Siis aitavad selles olukorras orienteeruda nooled, mis asuvad näiteks kõnealuse linnadiagrammi (graafiku) otse servadel – tänavatel.

Graafi, mille servades on nooled, nimetatakse orienteeritud.

Tootlusmäär suunatud graafi tipp on servade arv, mille jaoks see tipp on algus (servade arv, " välja tulema"algusest).

Sisenemise aste suunatud graafi tipp on servade arv, mille jaoks see tipp on lõpp (servade arv, " sissetulevad"ülaossa).

Jah, edasi Joonis 15 näitab suunatud graafikut ABCD. Mõnede selle tippude sisenemis- ja väljumisastmed on järgmised:
St.in.A=2, St.out.A=1 St.in.B=2, St.out.B=0 St.in.D=1, St.out.D=3.

Suunatud graafi tee tipust A1 tippu An on orienteeritud servade A1A2, A2A3, ..., Аn-1Аn jada, milles iga eelmise serva lõpp langeb kokku järgmise algusega ja iga serv esineb seda jada ainult üks kord.

Peal joonis.15 on näidatud suunatud graafiku teede näited. Pealegi on kaks esimest teed lihtsad - ükski tipp ei sisaldu selles rohkem kui üks kord. Kolmas viis pole lihtne, s.t. kuni. läbi tipu G tee " möödas"kaks korda.

Suunatud tsükkel nimetatakse suunatud graafikus suletud teeks.

Peal Joonis 15 Orienteeritud tsüklite näited on toodud kahel viimasel graafikul. Tsüklil, nagu igal teisel graafiku teekonnal, on pikkus, mille määrab selle tee servade arv.

Nii et joonisel 16 võivad teed A-st D olla erinevad ja erineva pikkusega.
Esimese tee pikkus on 2, teise - 3,
ja kolmas on 4.

Kahe tipu vahelise "lühema tee" pikkust nimetatakse nendevaheliseks kauguseks. Seega on joonise 16 graafiku tippude A ja D vaheline kaugus 2; kirjutatud nii: S(BP)=2.

Kui suunatud graafis ei ole võimalik ühest tipust teise “üle minna”, siis nimetatakse nendevahelist kaugust lõpmatuks (näidatud lõpmatuse sümboliga). Seega on joonisel 17 kujutatud graafiku tippude B ja D vaheline kaugus lõpmatu: S(DB) = ∞

Suunatud graafikuid majanduses kasutatakse aktiivselt võrguplaneerimisel, matemaatikas - mänguteoorias, hulgateoorias; paljude probleemide, eriti kombinatoorsete probleemide lahendamisel.

GRAAFIKUD

Graafikud tekkisid XVIII sajandil, kui kuulus matemaatik Leonhard Euler püüdis lahendada nüüdseks klassikalist Königsbergi sildade probleemi. Sel ajal Königsbergi linnas seal oli kaks saart, mis olid seitsme sillaga ühendatud Pregoli jõe kallaste ja üksteisega, nagu on näidatud joonisel fig. 7.1. Ülesanne on järgmine: viia läbi jalutuskäik linnas nii, et pärast iga silla täpselt ühe korra kõndimist jõuate tagasi samasse kohta, kust jalutuskäik algas. Selle ülesande lahendamisel kujutas Euler Koenigsbergi graafina, identifitseerides selle tipud linnaosadega ja servad neid osi ühendavate sildadega. Nagu näeme punktis 7.1, suutis Euler tõestada, et soovitud marsruuti mööda linna ei eksisteeri.

Joonis 7.1. Vana Koenigsbergi skeem

Selles peatükis tutvustame graafiteoorias kasutatavat standardterminoloogiat ja uurime mitmeid spetsiifilisi probleeme, mida saab graafikute abil lahendada. Eelkõige tutvustatakse meile graafikute klassi, mida nimetatakse puudeks. Puud on loomulik mudel, mis esindab andmeid, mis on organiseeritud hierarhilises süsteemis. Puuotsing üksikute üksuste isoleerimiseks ja andmete sortimine puus on arvutiteaduses olulised jõupingutused. Selle peatüki lisas vaatleme puudeks organiseeritud andmete sorteerimist ja otsimist.

Graafikud ja terminoloogia

Joonisel fig. 7.1 näitab Königsbergi seitset silda selliselt. kuidas need XVIII sajandil asusid. Probleem, mida Euler käsitles, küsib: kas on võimalik leida kõnnimarsruuti, mis kulgeb täpselt üks kord üle iga silla ning algab ja lõpeb linnas samas kohas?

Ülesande mudel on graafik, koosneb paljudest tipud ja paljud ribid tippude ühendamine. Tipud A, B, C ja D sümboliseerivad jõe ja saarte kaldaid ning ribisid a,c, c,d,f Ja g kujutavad seitset silda (vt joonis 7.2). Vajalik marsruut (kui see on olemas) vastab graafiku servade läbimisele nii, et igaüks neist läbitakse ainult üks kord. Ribi läbimine vastab ilmselgelt sillaga jõe ületamisele.

Joonis 7.2. Königsbergi silla probleemi mudel

Graafi, millel on marsruut, on marsruut, mis algab ja lõpeb samas tipus ning läbib graafiku kõiki servi täpselt ühe korra, nimetatakse Seileri graafik. Tippude jada (võib-olla kordustega), mida soovitud marsruut läbib, nagu ka marsruut ise, nimetatakse Eulerian tsükkel. Euler märkas, et kui graafis on Euleri tsükkel, siis iga mingisse tippu viiva serva jaoks peab sellest tipust 1 lahkuma veel üks serv ning sellest lihtsast tähelepanekust tegi ta järgmise järelduse: kui graafikus on Euleri tsükkel. antud graafik , siis peab igal tipul olema paarisarv servi.

Lisaks suutis Euler tõestada vastupidist väidet, nii et graaf, milles mis tahes tippude paar on ühendatud mingi servajadaga, on Euleri siis ja ainult siis, kui kõik selle tipud on paarisastmega. Kraad tipud v nimetatakse arvuks δ(v) ribid, tema intsident 2 .

Nüüd on täiesti ilmne, et Königsbergi sillaprobleemi modelleerivas graafikus ei leita Euleri tsüklit. Tõepoolest, kõigi selle tippude astmed on paaritud: δ(B) = δ(C)= δ(D) = 3 ja δ(A) = 5. Euleri abiga hakati paljude praktiliste ülesannete lahendamisel kasutama sarnaseid graafikuid, mida uurisime sildade ülesande lahendamisel ja nende uurimine kasvas oluliseks matemaatikavaldkonnaks.

Lihtne graafik on defineeritud kui paar G = (V, E), kus V on tippude lõplik hulk ja E- lõplik servade hulk ja ei saa sisaldada silmuseid(sama tipuga algavad ja lõppevad servad) ja mitu serva(mitu serva on mitu serva, mis ühendavad sama tipupaari). Joonisel fig. 7.2. ei ole lihtne, kuna näiteks tipud A Ja IN on ühendatud kahe servaga (just neid servi nimetatakse mitmeks).

Kaks tippu u Ja v lihtsas graafikus nimetatakse külgnevad, kui need on mõne servaga ühendatud e, mille kohta nad ütlevad, et see on juhuslik tipp u (ja v ). Nii võime ette kujutada paljusid E servad kõrvuti asetsevate tippude paaride kogumina, määratledes seeläbi hulga mitterefleksiivse sümmeetrilise seose V. Refleksiivsuse puudumine on tingitud sellest, et lihtsas graafis pole silmuseid ehk servi, mille mõlemad otsad on samas tipus. Suhte sümmeetria tuleneb sellest, et serv e, ühendab tippu Ja Koos v,ühendab ja v Koos Ja(teisisõnu, servad ei ole orienteeritud, st neil puudub suund). Üks serv lihtsas graafis, mis ühendab tippupaari u Ja v, tähistame seda kui jav(või vi).

Graafi tippude hulgal oleva seose loogilist maatriksit, mis on määratletud selle servadega, nimetatakse ,külgnemismaatriks. Seose sümmeetria külgnemismaatriksi M järgi tähendab, et M sümmeetriline põhidiagonaali suhtes. Ja selle suhte mitterefleksiivsuse tõttu maatriksi M põhidiagonaalil seal on sümbol "L".

Näide 7.1. Joonistage graafik G(V, E) tippude hulgaga V = (a, b, c, d, e) ja servade komplekt E = (ab, ae, bc, bd, ce, de). Kirjutage üles selle naabrusmaatriks.

Lahendus. Graafik G on näidatud joonisel fig. 7.3.

Joonis 7.3.

Selle naabrusmaatriks on järgmisel kujul:

Graafi taastamiseks vajame ainult neid naabrusmaatriksi elemente, mis on põhidiagonaalist kõrgemal.

Alamgraafik graafikut G = (V, E) nimetatakse graafikuks G’ = (V’, E’), milles E’ C E ja V’ C V.

Näide 7.2 Leidke joonisel fig. 7.4, graafiku G alamgraafikud.

Lahendus. Tähistame graafikute G, H ja K tipud, nagu on näidatud joonisel fig. 7.5. Graafikud H ja K on G alamgraafid, nagu meie tähistusest näha. Graaf L ei ole G alamgraaf, kuna sellel on tipp indeksiga 4, G-l aga mitte.

Tee pikkus k graafis G nimetatakse sellist tippude jada v 0 , v 1 , …, v k , et iga i = 1, …, k paar v i – 1 v i moodustab graafiku serva. Sellist marsruuti tähistame tähisega v 0 v 1 … v k . Näiteks 1 4 3 2 5 on näite 7.2 graafikul G marsruut pikkusega 4.

G H

K L

Joonis 7.4.

Tsükkel graafis on tavaks nimetada tippude jada v 0 , v 1 , … , v k , mille iga paar on ühe serva otsad ja v 0 = v 1 , ja ülejäänud tippe (ja servi) ei korrata. Teisisõnu, tsükkel on suletud marsruut, mis läbib selle iga tippu ja serva ainult üks kord

1 2 1 2 3

Joonis 7.5

Näide 7.3. Leia näite 7.2 graafikult G tsüklid.

Lahendus. Sellel graafikul on kaks erinevat tsüklit pikkusega 5:

1 3 2 5 4 1 ja 1 2 5 4 3 1

Me saame läbida need tsüklid ühes või teises suunas, alustades tsükli suvalisest tipust. Lisaks on graafikul kolm erinevat tsüklit pikkusega 4:

1 2 5 4 1, 1 2 3 4 1 ja 2 5 4 3 2,

ja kaks silmust pikkusega 3:

1 2 3 1 ja 1 3 4 1.

Graafi, millel pole tsükleid, nimetatakse atsükliline. Arvutamisel tekkivad puustruktuurid on atsükliliste graafikute erijuht. Me käsitleme neid hiljem selles peatükis.

Count, helistas sidus, kui mõni selle tippude paar on ühendatud mingi marsruudiga. Iga üldgraafiku saab jagada alamgraafikuteks, millest igaüks osutub seotuks. Nimetatakse selliste ühendatud komponentide minimaalne arv ühenduse number graafik ja seda tähistatakse c(G) . Ühenduvusprobleemid on olulised graafikuteooria rakendustes arvutivõrkudele. Graafiku ühenduvusnumbri määramiseks kasutatakse järgmist algoritmi.

Ühenduvusalgoritm.

Olgu G = (V, E) graafik. Algoritm on loodud väärtuse arvutamiseks c = c(G), need. antud graafiku G ühendatud komponentide arv.

V' :=V;

samasV’≠ øteha

Valige y Є V’

Leia marsruuti y-ga ühendavad tipud;

Eemalda tipustV' Ja

vastavad servad E-st;

c:= c+1;

Näide 7.4. Jälgige ühenduvusalgoritmi tööd joonisel fig. 7.6.

Joonis 7.6.

Lahendus. Vaata tabelit. 7.1.

Tabel 7.1.


Algväärtused	{1,2,3,4,5,6,7,8}
Valik y = 1
Valik y = 2
Valik y = 7

Niisiis, c(G) = 3. Vastavad ühendatud komponendid on näidatud joonisel fig. 7.7.

Riis. 7.1

II. GRAAFISTEOORIA ELEMENTID

§ 7. Graafikute põhimõisted ja tüübid

1. Põhimõisted

Olgu V lõplik mittetühi hulk ja E ((u, v) u,v V, u ≠ v) selle kaheelemendiliste alamhulkade hulk. Paari G = (V, E) nimetatakse graafikuks. Hulka V = V (G) nimetatakse graafi G tippude hulgaks ja selle elemente tippudeks; hulka E = E (G) nimetatakse graafi G servade hulgaks ja selle elemente servadeks. Graafi G tippe ja servi nimetatakse selle elementideks. Seega, kui u on graafi G tipp ja e on G serv, siis u V (G), e E (G) asemel saame kirjutada u G, e G.

Kui e = (u, v) on graafi G serv (kirjutatakse ka e = uv), siis nimetatakse tippe u ja v serva e otsteks.

Graafe on mugav kujutada jooniste kujul, millel märgitud punktid (või ringid) vastavad tippudele ja vastavaid tippe ühendavad pidevad jooned vastavad servadele (vt joonis 7.1).

Graafi G tippe u ja v nimetatakse külgnevateks, kui (u, v) E (G), s.t. kui need on servaga ühendatud. Kaht serva nimetatakse omakorda kõrvutiseks, kui neil on ühine ots. Kui tipp v on serva e lõpp, siis v

ja e nimetatakse vahejuhtumiks.

Tippude hulga V(G) kardinaalsust V(G) nimetatakse graafi G järku ja tähistatakse G-ga. Kui V (G) = n ja E (G) =m, siis nimetatakse graafikut G (n,m)-graafikuks.

2. Graafikute põhitüübid

Graafi nimetatakse tühjaks, kui E (G) = , st kui sellel pole servi. Tühja graafiku järku n tähistatakse 0 n-ga. Graafikut 0 1 nimetatakse triviaalseks. Graafi, milles mis tahes kaks tippu on servaga ühendatud, nimetatakse täielikuks. Täielikku n-järku graafikut tähistab K n (joon. 7.2 – 7.5).

Graafik, nagu joonisel fig. 7.6 nimetatakse lihtsaks vooluringiks. Lihtahelat järku n tähistatakse tähega P n (joonis 7.6 näitab ahelat P 4 ). Lihtahelal P n on n – 1 serva.

Riis. 7.9

Suletud ahelad, s.o. sellised graafikud nagu joonisel fig. 7.7 kutsutakse lihtsad silmused. Lihttsüklit järku n tähistatakse tähega C n (joonis 7.7 kujutab lihtsat ahelat C 7 ). On selge, et lihtsal ahelal C n on sama palju servi kui tippe, s.t. n.

Graafikud nagu joonisel fig. 7.8 nimetatakse ratasteks. Ratas suurusjärgus n +1 on tähistatud W n-ga (ratas W 7 on näidatud joonisel 7.8); sellel on 2n serva.

Graafi nimetatakse kahepoolseks, kui selle tippude hulka saab jagada kaheks mittetühjaks alamhulgaks (osaks), nii et kaks sama osa tippu ei asu kõrvuti. (Kolmeosalised, neljapoolsed jne graafikud on defineeritud sarnaselt.) Seega võivad kahepoolses graafis olla kõrvuti ainult erinevatest osadest pärit tipud (mitte tingimata igaüks neist). Kahepoolse graafiku näidet vt joonis fig. 7.9.

Kui kahepoolses graafis on mis tahes kaks tippu erinevatest osadest ühendatud servaga, siis sellist graafi nimetatakse täielik kaheiduleht.

Täielikku kahepoolset graafi, mille ühes osas on n ja teises osas m tippu, tähistatakse K n,m . Vaadake joonisel fig. 7.10 – 7.12.

K 2.2	K 2.3	K 3.3

Graafe K 1, n nimetatakse tähtgraafikuteks ehk tähtedeks.

On hästi näha, et graafik K n,m on (n+m, nm)-graaf, s.t. on n+m tippu ja nm servi.

On selge, et on graafikuid, mida saab samaaegselt liigitada mitut tüüpi. Näiteks K 3 = C 3, K 2 = P 2, K 2, 2 = C 4, K 4 = W 3.

3. Graafi mõiste üldistused

Graafi definitsioon lõikes 1 eeldab, et mis tahes tippude paari saab ühendada maksimaalselt ühe servaga. Küll aga on probleeme ja graafikute näiteid

Riis. 7.16

kui on vaja lubada mitme serva olemasolu sama tipupaari vahel. Selliseid servi nimetatakse kordadeks. Mitme servaga graafikut nimetatakse multigraafiks (joonis 7.14). Algsele definitsioonile vastavaid graafikuid (juhul, kui on vaja rõhutada, et neil pole mitut serva) nimetatakse nn. lihtsad graafikud(Joon. 7.13). Lisaks on mõnikord vaja arvestada vormi (v, v) servadega, mis ühendavad tippu v iseendaga. Selliseid servi nimetatakse silmusteks. Silmustega multigraafi nimetatakse pseudograafiks (joon. 7.15.).

Kutsutakse paari (V, E), kus V on mittetühi hulk ja E V 2 suunatud graafik(või lühidalt: digraaf). Sellise graafiku servad on vormi orienteeritud (st järjestatud) paarid

(u, v). Sel juhul nimetatakse tippu u serva alguseks ja v on lõpp. Orienteeritud servi nimetatakse kaaredeks ja neid kujutatakse joontena nooltega, mis näitavad suunda serva algusest lõpuni

Kaari (u, v) ja (v, u), mis ühendavad sama tipupaari, kuid millel on vastassuunad, nimetatakse sümmeetrilisteks.

Vaadelda võib mitte ainult lihtdigraafe, vaid ka suunatud multi- ja pseudograafe.

Mõnikord määratakse teatud ülesannete lahendamisel servadele ja (või) tippudele teatud numbrid. Olenemata nende konkreetsest tähendusest nimetatakse selliseid numbreid kaaludeks (tipu kaal, serva kaal) ja saadud graafikut nimetatakse kaalutud graafik.

Reeglina on teatud teemade uurimisel eelnevalt (või on kontekstist selge) täpsustatud, milliste graafikute üle arutletakse. Sel juhul nimetatakse neid lihtsalt graafikuteks ilma eesliideteta "multi-", "pseudo-" jne.

4. Isomorfsed graafikud

Graafikute üks omadus on see, et neid tasapinnal kujutades ei ole üldse oluline, kuidas tipud üksteise suhtes paiknevad. Seetõttu võib üks ja sama graafik vastata selle erinevatele kujutistele. Lisaks on just sellised joonised kõige lihtsamad täpsustamisviisid

graafikuid nimetatakse sageli graafikuteks. Et eristada samale graafikule vastavaid jooniseid erinevaid graafikuid kujutavatest joonistest, tutvustame järgmist mõistet.

Definitsioon . Kaks graafikut G ja H on isomorfsed, kui on olemas bijektsioon f: V(G) → V(H), mis säilitab külgnevuse, s.t. bijektiivne kaardistus, mille kohaselt graafi G tippude v ja u kujutised on H-s kõrvuti siis ja ainult siis, kui u ja v on graafis G kõrvuti. Kutsutakse välja antud omadusega vastendus f

isomorfism.

Kui graafikud G ja H on isomorfsed, siis kirjutage G H .

Näiteks kõik kolm graafikut joonisel fig. 7,17-7,19 on üksteise suhtes isomorfsed (isomorfismi määrab tippude numeratsioon).

Ilmselgelt on isomorfismi relatsioon graafikute komplektil ekvivalentsuseos (see on refleksiivne, sümmeetriline ja transitiivne). Järelikult jagatakse kõigi graafikute hulk isomorfsete graafikute klassideks nii, et erinevad klassid ei ristuks. Loomulik on tuvastada kõik ühte klassi kuuluvad graafikud, s.t. peetakse identseteks (need võivad erineda ainult oma elementide mustri või olemuse poolest). Juhtudel, kui on vaja rõhutada, et vaadeldavad graafikud erinevad ainult isomorfismini, on tavaks rääkida " abstraktsed graafikud". Põhimõtteliselt on abstraktne graaf isomorfsete graafikute klass.

Mõnes olukorras on siiski vaja eristada isomorfseid graafikuid ja siis tekibki mõiste “märgistatud graaf”. Graafi, mille järjekord on n, nimetatakse märgistatuks, kui selle tippudele on omistatud sildid, näiteks numbrid 1, 2, 3, ..., n. Sel juhul identifitseeritakse graafi G tipud nende arvudega, s.t. arvatakse, et V (G) = (1, 2, 3, ..., n).

Graafide tüübid saab määrata nende konstrueerimise üldpõhimõtete järgi (näiteks kahepoolne graaf ja Euleri graaf) või need võivad sõltuda tippude või servade teatud omadustest (näiteks suunatud ja suunamata graaf, tavaline graaf graafik).

Suunatud ja suunamata graafikud

lingid(graafiku serva kahe otsa järjekord ei ole oluline) kutsutakse orienteerimata .

Graafikud, millel on kõik servad kaared(graafiku serva kahe otsa järjekord on oluline) kutsutakse suunatud graafikud või digraafid .

Suunamata graafik saab esitada kujul suunatud graafik , kui selle iga lüli asendatakse kahe vastassuunalise kaarega.

Tsükkelgraafikud, segagraafikud, tühjad graafikud, multigraafid, tavalised graafikud, täielikud graafikud

Kui graafik sisaldab silmuseid, siis on see asjaolu spetsiaalselt ette nähtud, lisades graafiku põhitunnustele sõnad "silmustega", näiteks "silmustega digraaf". Kui graafik ei sisalda silmuseid, lisatakse sõnad "silmusteta".

Segatud on graafik, mis sisaldab kolmest mainitud tüübist (lingid, kaared, tsüklid) vähemalt kahe servi.

Graafik, mis koosneb ainult paljad tipud, kutsus tühi .

Multigraaf on graaf, milles tippude paare saab ühendada rohkem kui ühe servaga, st sisaldada mitu serva, kuid ei sisalda silmuseid.

Kutsutakse ilma kaareta (st suunamata), silmuste ja mitme servata graafikut tavaline . Tavaline graafik on näidatud alloleval joonisel.

Nimetatakse antud tüüpi graafikut täielik , kui see sisaldab kõiki selle tüübi jaoks võimalikke servi (konstantse tippude komplektiga). Seega on täielikus tavalises graafikus iga erinevate tippude paar ühendatud täpselt ühe lingiga (joonis allpool).

Kahepoolne graafik

Graafikut nimetatakse kahepoolseks , kui selle tippude hulga saab jagada kaheks alamhulgaks nii, et ükski serv ei ühenda sama alamhulga tippe.

Näide 1. Ehitada täis kahepoolne graafik.

Täielik kahepoolne graaf koosneb kahest tippude hulgast ja kõigist võimalikest linkidest, mis ühendavad ühe hulga tippe teise hulga tippudega (joonis allpool).

Euleri graafik

Oleme juba puudutanud probleeme Königsbergi sildadega. Euleri negatiivne lahendus sellele probleemile viis esimese avaldatud tööni graafiteooria kohta. Silla läbimise probleemi saab üldistada järgmiseks graafiteooria ülesandeks: Kas antud graafist on võimalik leida tsükkel, mis sisaldab kõiki tippe ja kõiki servi? Graafi, milles see on võimalik, nimetatakse Euleri graafikuks.

Niisiis, Euleri graafik on graaf, milles saab läbida kõik tipud ja samal ajal läbida ühe serva ainult ühe korra. Selles peab igal tipul olema ainult paarisarv servi.

Näide 2. On sama numbriga täielik graafik n servad, kuhu iga tipp langeb, kas Euleri graaf? Selgitage vastust. Too näiteid.

Vastus. Kui n on paaritu arv, siis on iga tipp juhuslik n-1 ribi. Sel juhul on antud graaf Euleri graaf. Selliste graafikute näited on toodud alloleval joonisel.

Tavaline graafik

Regulaarne loendus on ühendatud graaf, kus kõigil tippudel on sama aste k. Seega on joonisel 2 toodud näited korrapärastest graafikutest, mida nimetatakse 4-regulaarseteks ja 2-regulaarseteks graafikuteks või 4. ja 2. astme regulaargraafikuteks vastavalt nende tippude astmele.

Tavalise graafiku tippude arv k- kraad ei saa olla väiksem k+1. Tavalisel paaritu astmega graafikul võib olla ainult paarisarv tippe.

Näide 3. Koostage tavaline graafik, mille lühima tsükli pikkus on 4.

Lahendus. Arutleme järgmiselt: selleks, et tsükli pikkus vastaks antud tingimusele, on vajalik, et graafiku tippude arv oleks neljakordne. Kui tippude arv on neli, saate alloleval joonisel näidatud graafiku. See on regulaarne, kuid selle lühima tsükli pikkus on 3.

Suurendame tippude arvu kaheksani (järgmine arv on neljakordne). Ühendame tipud servadega nii, et tippude astmed on võrdsed kolmega. Saame järgmise graafiku, mis vastab ülesande tingimustele.

Hamiltoni krahv

Hamiltoni krahv on graafik, mis sisaldab Hamiltoni tsüklit. Hamiltoni tsükkel nimetatakse lihtsaks tsükliks, mis läbib vaadeldava graafi kõiki tippe. Seega lihtsustatult öeldes on Hamiltoni graaf graaf, mille kõik tipud on läbitavad ja iga tippu korratakse läbimisel ainult üks kord. Hamiltoni graafiku näide on alloleval joonisel.

Näide 4. Antud kahepoolne graafik, milles n- tippude arv hulgast A, A m- tippude arv hulgast B. Millisel juhul on graaf Euleri ja millisel juhul Hamiltoni graaf?