Mitteametlikult võib graafikut pidada punktide ja joonte kogumina, mis neid punkte ühendavad, nooltega või ilma.
Graafiteooria kui matemaatilise distsipliini esimeseks teoseks peetakse Euleri tööd (1736), mis käsitles Köningsbergi sildade probleemi. Euler näitas, et iga silda täpselt ühe korra ületades on võimatu mööda minna seitsmest linnasillast ja naasta alguspunkti. Graafiteooria sai järgmise tõuke ligi 100 aastat hiljem elektrivõrkude, kristallograafia, orgaanilise keemia ja teiste teaduste alaste uuringute arenemisega.
Märkamatult kohtame graafikuid kogu aeg. Näiteks graafik on metrooliinide diagramm. Sellel olevad punktid tähistavad jaamu ja jooned rongimarsruute. Uurides oma esivanemaid ja tuues selle kauge esivanema juurde, ehitame nn sugupuu. Ja see puu on graafik.
Graafikud on mugav vahend objektide vaheliste suhete kirjeldamiseks. Oleme varem kasutanud graafikuid lõplike binaarsuhete visuaalseks esitamiseks.
Kuid graafikut ei kasutata mitte ainult illustratsioonina. Näiteks asustatud alade vahelist teedevõrku kujutavat graafikut vaadeldes saate määrata marsruudi punktist A punkti B. Kui selliseid marsruute on mitu, siis soovite valida teatud mõttes optimaalse, näiteks kõige lühem või ohutum. Valikuülesande lahendamiseks on vaja graafikutel läbi viia teatud arvutused. Selliste ülesannete lahendamisel on mugav kasutada algebralisi võtteid ja graafiku kontseptsioon vajab vormistamist.
Graafiteooria meetodeid kasutatakse diskreetses matemaatikas laialdaselt. Erinevate diskreetsete muundurite analüüsimisel ja sünteesimisel ei saa ilma nendeta hakkama: arvutite funktsionaalsed plokid, tarkvarapaketid jne.
Praegu hõlmab graafiteooria palju materjali ja see areneb aktiivselt. Selle esitamisel piirdume vaid osa tulemustega ning paneme põhirõhu mõne laialt levinud graafianalüüsi algoritmi kirjeldamisele ja põhjendamisele, mida kasutatakse formaalsete keelte teoorias.
Põhimääratlused
Graafikud, nagu näidetes juba märgitud, on teatud objektide vaheliste ühenduste „visualiseerimiseks“. Need ühendused võivad olla „suunatud“, näiteks sugupuus, või „suunamata“ (kahesuunaline võrk). teed). Selle kohaselt on graafiteoorias kaks peamist tüüpi graafikuid: suunatud (või suunatud) ja suunamata.
Esitlusmeetodid
Seni oleme määratlenud suunatud ja suunamata graafikud, kujutades neid jooniste abil. Graafi saab defineerida ka hulga paarina, järgides definitsiooni, kuid see meetod on üsna tülikas ja pakub pigem teoreetiliselt huvi. Graafikute omaduste analüüsi algoritmiliste lähenemisviiside väljatöötamine eeldab graafikute kirjeldamiseks muid, praktilisteks arvutusteks sobivamaid viise, sh arvuti kasutamist. Vaatame kolme levinumat graafikute esitamise viisi.
puud
Definitsioon 5.5. Suunamata puu on ühendatud ja atsükliline suunamata graaf. Definitsioon 5.6. Suunatud puu on mittekontuuriga suunatud graaf, milles ühegi tipu poolkraad ei ole suurem kui 1 ja seal on täpselt üks tipp, mida nimetatakse suunatud puu juureks, mille poolkraad on 0.
Väikseima kaaluga laiuv puu
Järgmist ülesannet tuntakse graafiteoorias Steineri probleemina: tasapinnal on antud n punkti; peate need ühendama sirgete segmentidega nii, et segmentide kogupikkus oleks minimaalne.
Graafi tippude süstemaatilise läbimise meetodid
Graafiteooria olulised probleemid on nii suunamata kui ka suunatud graafide globaalse analüüsi probleemid. Nende ülesannete hulka kuuluvad näiteks tsüklite või kontuuride leidmise ülesanne, tipupaaride vaheliste teede pikkuste arvutamine, teatud omadustega teede loetlemine jne. Globaalset graafianalüüsi tuleks eristada lokaalsest analüüsist, mille näide on suunatud graafi fikseeritud tipu eelkäijate ja järglaste hulkade määramise probleem.
Teeprobleem kaalutud suunatud graafikutes
Graafiline isomorfism
Suunatud graafi (V, E) korral võib kaarede hulka E käsitleda tippude hulgal defineeritud binaarse otsesaadavuse seose graafikuna. Suunamata graafis (V, E) on servade hulk E järjestamata paaride hulk. Iga järjestamata paari (u, v) ∈ E korral võime eeldada, et tipud u ja v on ühendatud sümmeetrilise binaarseosega p, s.t. (u, v) ∈ р ja (v, u) ∈ р.
Topoloogiline sorteerimine
Definitsioon 5.17. Suunatud võrk (või lihtsalt võrk) on kontuurideta suunatud graafik*. Kuna võrk on kontuurideta graaf, siis on võimalik näidata, et võrgus on nii nulli väljaminekuga tippe (sõlmi), kui ka null-sisendastmega tippe (sõlmi). Esimesi nimetatakse võrgu valamuteks või väljunditeks ja teisi võrgu allikateks või sisenditeks.
Tsüklomaatika elemendid
Suunatamata graafis sügavus-esimese otsingu algoritmi käsitlemisel käsitleti graafi nn fundamentaalsete tsüklite otsimise küsimust. Sel juhul mõisteti põhitsükli all tsüklit, mis sisaldab täpselt ühte pöördserva ning põhitsüklite ja pöördservade vahel loodi üks-ühele vastavus; põhitsüklid tekivad alati, kui suunamata graafiku kõik servad jaotatakse meelevaldselt puud (moodustades mingi algse graafi maksimaalse servametsa) ja pöördvõrdeline ning üldjuhul saab selle partitsiooni määrata täiesti sõltumatult sügavus-esimese otsingu algoritmist. Sügavuspõhine otsing on vaid üks viis sellise partitsiooni rakendamiseks.
Graafiteooria on matemaatika haru, mida kasutatakse arvutiteaduses ja programmeerimises, majanduses, logistikas ja keemias.
Mis on graafik
Graafilisi diagramme kasutatakse sageli süsteemide struktuuri kirjeldamiseks. Neis olevad elemendid on kujutatud ringide, punktide, ruutudega jne ning elementide vahelisi seoseid joonte või nooltega. Sel juhul pole oluline ei elementide kujutamine ega joonte pikkus või kuju – loeb vaid see, millised elemendid on omavahel ühendatud. Seega on graaf kujul (A, M) paar, kus A on lõplik tippude hulk ja M on servade kogum - mõnda tippu ühendav joon.
Graafiteooria põhimõisted
Orienteeritud graafikul või digraafil (vt joonist allpool) on orienteeritud servad, mida nimetatakse kaarteks ja mida kujutatakse nooltega. Kaart saab tähistada järjestatud tippude paariga, mida see ühendab, alguse ja lõpuga.
Suunamata graafikul (vt joonist allpool) on servad, mis joonistatakse joontena ilma orientatsioonita. Vastavalt sellele on servaga ühendatud tippude paar järjestamata. Mõlemad tipud on serva otsad.
Kui tipud a ja b on graafi serva (või kaare alguse ja lõpu) otsad, siis öeldakse, et tipud a ja b langevad sellele servale (kaarele) ja serv (kaar) on samuti intsident tippudele a ja b. Kui tipud a ja b on serva otsad, siis nimetatakse neid (a ja b) külgnevateks.
Kõige sagedamini vaatleme graafikuid, mille servad on ühte tüüpi - kas need on suunatud või mitte.
Kui servadel on sama algus ja lõpp, siis nimetatakse neid mitmeks servaks ja graafikut, milles need asuvad, nimetatakse multigraafiks.
Graafiteooria kasutab ka mõistet "silmus" – serv, mis läheb välja ja läheb samasse tippu. Graafi, millel on silmused, nimetatakse pseudograafiks.
Kõige levinumad on suunamata graafikud, millel pole mitut serva ega silmust. Selliseid graafikuid nimetatakse tavalisteks. Neil ei ole mitut serva, nii et saame tuvastada serva ja vastava tippude paari.
Iga digraafi tippu iseloomustavad:
- Pool tulemust. See on sellest väljuvate kaarte arv.
- Pool lähenemisastet. See on antud tippu sisenevate kaarede arv.
Digraafi sisestamise poolkraadide summa ja ka tulemuse poolkraadide summa on võrdne graafiku kaare koguarvuga.
Suunamata graafis iseloomustab iga tippu tipu aste. See on tippu langevate servade arv. Graafi tippude astmete kogusumma on servade arv korrutatuna kahega: iga serv annab panuse, mis on võrdne kahega.
0 kraadiga tippu nimetatakse isoleeritud.
Rippuv tipp on 1. astmega tipp.
Graafiteooria nimetab tühjaks graafikuks sellist, millel puuduvad servad. Tervikgraaf on tavaline graaf, mille 2 tippu on kõrvuti.
Kaalutud graafikud on graafikud, mille tippudele või servadele (kaared) või mõlemale tippudele ja servadele (kaared) korraga on määratud teatud numbrid. Neid nimetatakse kaaludeks. Teisel joonisel on kujutatud suunamata graafik, mille servad on kaalutud.
Graafikud: isomorfism
Matemaatikas kasutatakse isomorfismi mõistet. Täpsemalt, graafiteooria defineerib seda järgmiselt: kaks graafi U ja V on isomorfsed, kui nendes graafides on nende tippude hulkade vahel bijektsioon: graafi U iga 2 tippu on ühendatud servaga siis ja ainult siis, kui Graaf V samad on ühendatud servatippudega (millel võivad olla erinevad nimed). Alloleval joonisel on kujutatud kaks isomorfset graafikut, kus ülalkirjeldatud bijektsioon eksisteerib nii esimese kui ka teise graafiku samade värvidega tippude vahel.
Rajad ja tsüklid
Tee suunamata või suunatud graafis on servade jada, kus iga järgmine algab tipust, kus eelmine lõpeb. Lihtne tee on selline, mille kõik tipud, välja arvatud ehk algus ja lõpp ning servad, on erinevad. Tsükkel digraafis on tee, mille algus- ja lõpptipud langevad kokku ja mis sisaldab vähemalt ühte serva. Tsükkel suunamata graafis on tee, mis sisaldab vähemalt kolme erinevat serva. Teisel joonisel on tsükliks näiteks tee (3, 1), (6, 3), (1, 6).
Graafiteooriat programmeerimises kasutatakse algoritmide graafiku diagrammide koostamiseks.
K. Berge raamat on esimene venekeelne graafiteooria raamat. Samal ajal on viimastel aastatel huvi teooria vastu järsult kasvanud nii matemaatikute kui ka väga erinevate teadusharude esindajate poolt. Seda seletatakse sellega, et graafiteooria meetodid lahendavad edukalt arvukalt probleeme elektriahelate teoorias, transpordiahelate teoorias, infoteoorias, küberneetikas jne.
Berge raamatus esitatakse graafiteooriat järjestikku, alustades päris põhitõdedest. Eeldatakse, et lugejal on väga tagasihoidlikud matemaatilised teadmised, kuigi tal on teatud matemaatikakultuur. Tekst sisaldab arvukalt, sageli naljakaid näiteid. Raamatut saab kasutada graafiteooria esmaseks uurimiseks. Ka professionaalsed matemaatikud leiavad sealt palju huvitavat.
Algoritm Euleri tsükli otseseks tuvastamiseks.
[Fleury]. Vaatleme ühendatud multigraafi G, mille kõik tipud on paarisastmega, ja proovime seda joonistada ühe tõmbega, kasutamata ehitusprotsessi käigus juba joonistatud trajektoori osas parandusi. Piisab, kui järgite järgmist reeglit:
1 Väljume suvalisest tipust a; Kriipsutame maha iga läbitud serva.
2 Me ei lähe kunagi mööda sellist serva ja mis hetkel on maakitsus (st eemaldamisel jaguneb risttamata servadest moodustatud graaf kaheks ühendatud komponendiks, millest kummalgi on vähemalt üks serv),
Seda reeglit järgides oleme alati soodsas positsioonis, sest kui oleme punktis x = a, on (ristamata servade) graafikul kaks paaritu astme tippu: x ja a; kui eraldatud tipud kõrvale jätta, jääb alles ühendatud graaf, millel on teoreemi 1 kohaselt Euleri ahel, mis algab punktist x.
Sisu
Sissejuhatus
Peatükk 1. Põhimõisted
Komplektid ja mitme väärtusega vastendused
Graafik. Rajad ja kontuurid
Vooluahelad ja tsüklid
Peatükk 2. Kvaasikorrapärasuse eeluuring
Graafiga määratletud kvaasijärjekord
Induktiivne graafik ja alused
3. peatükk. Ordinaalfunktsioon ja funktsioon
Grundy lõpmatu graafiku jaoks
Üldised kaalutlused lõpmatute graafikute kohta
Tavaline funktsioon
Grundy funktsioonid
Tehted graafikutel
Peatükk 4. Graafiteooria põhiarvud
Tsüklomaatiline number
Kromaatiline arv
Sisemine stabiilsusnumber
Väline stabiilsusnumber
Peatükk 5. Graafiku tuumad
Olemasolu ja kordumatuse teoreemid
Rakendus Grundy funktsioonidele
Peatükk 6. Graafikumängud
Mäng Nim
Mängu üldine määratlus (koos täieliku teabega)
Strateegiad
Peatükk 7. Lühima tee probleem
Protsessid etappide kaupa Mõned üldistused
Peatükk 8. Transpordivõrgud
Maksimaalse voolu probleem Vähima vooluhulga probleem
Määratud väärtusega ühilduva voo probleem
Lõputud transpordivõrgud
9. peatükk. Poolastmete teoreem
Poole väljamineva ja sisenemise aste
Peatükk 10. Lihtsa graafiku sobitamine
Maksimaalne sobitamise probleem
Lihtne graafiku puudus
Ungari algoritm
Üldistus lõpmatule juhtumile
Rakendus maatriksiteooriale
Peatükk 11. Tegurid
Hamiltoni rajad ja Hamiltoni kontuurid
Faktori leidmine
Etteantud poolkraadidega osagraafiku leidmine
Peatükk 12. Graafikukeskused
Keskused
Raadius
Peatükk 13. Tugevalt seotud graafiku läbimõõt
Tugevalt seotud tsükliteta graafikute üldomadused
Läbimõõt
Peatükk 14. Graafiku külgnemismaatriks
Tavamaatrikstehte rakendamine
Probleemid loendamisega
Juhi probleem
Boole'i operatsioonide kasutamine
Peatükk 15. Juhtumimaatriksid
Täiesti unimodulaarsed maatriksid
Täiesti unimodulaarsed süsteemid
Tsüklomaatilised maatriksid
Peatükk 16. Puud ja esivanemate puud
puud
Analüütiline uurimus
Grandtrees
Peatükk 17. Euleri probleem
Euler tsüklib Euleri kontuure
Peatükk 18. Suvalise graafi sobitamine
Vahelduva vooluahela teooria
Etteantud tipukraadidega osagraafiku leidmine
Täiuslik sobitamine
Rakendus sisemisele stabiilsusnumbrile
Peatükk 19. Faktoroidid
Hamiltoni tsüklid ja faktorioidid
Faktoroidi olemasoluks vajalik ja piisav tingimus
Peatükk 20. Graafiku ühenduvus
Liigestuspunktid
Graafikud ilma liigendusteta
h-ühendatud graafikud
Peatükk 21. Tasapinnalised graafikud
Põhiomadused
Üldistus
Täiendused
I. Väljas üldteooria, mängud
II. Transpordiülesannetest
III. Võimalike kontseptsioonide kasutamisest transpordivõrkudes
IV. Lahendamata probleemid ja tõestamata oletused
V. Loendamise mõnest põhiprintsiibist (J. Riguet)
VI. Täiendused venekeelsele tõlkele (A.A. Zykov ja G.I. Kozhukhin)
Kirjandus
Graafiteooria ja C. Berge raamat (venekeelse tõlke järelsõna)
Tähemärgi indeks
Nimeregister
Õppeaine register.
Lae e-raamat mugavas vormingus tasuta alla, vaata ja loe:
Laadige kiiresti ja tasuta alla raamat Graafiteooria ja selle rakendused, Berge K. - fileskachat.com.
Graafiteooria on diskreetse matemaatika haru, mis uurib üksikute elementidena (tipudena) kujutatud objekte ja nendevahelisi seoseid (kaared, servad).
Graafiteooria pärineb Königsbergi sildade probleemi lahendamisest 1736. aastal kuulsa matemaatiku poolt. Leonard Euler(1707-1783: sündinud Šveitsis, elanud ja töötanud Venemaal).
Probleem Königsbergi sildadega.
Pregali jõe ääres asuvas Preisi linnas Königsbergis on seitse silda. Kas on võimalik leida jalgsi marsruut, mis ületab iga silla täpselt ühe korra ning algab ja lõpeb samas kohas?
Graafi, millel on marsruut, mis algab ja lõpeb samas tipus ning läbib graafiku kõiki servi täpselt ühe korra, nimetatakseEuleri graafik.
Tippude jada (võib-olla korduv), mida soovitud marsruut läbib, samuti marsruuti ennast nimetatakseEuleri tsükkel .
Kolme maja ja kolme kaevu probleem.
Seal on kolm maja ja kolm kaevu, mis paiknevad kuidagi lennukis. Joonista igast majast iga kaevu juurde tee, et teed ei ristuks. Selle probleemi lahendas (näitati, et lahendust pole) Kuratovski (1896 - 1979) 1930. aastal.
Nelja värvi probleem. Tasapinna jagamist mittelõikuvateks aladeks nimetatakse kaardiga. Kaardialasid nimetatakse külgnevateks, kui neil on ühine piir. Ülesanne on värvida kaart nii, et kaks kõrvuti asetsevat ala ei oleks värvitud sama värviga. Alates 19. sajandi lõpust on teada hüpotees, et selleks piisab neljast värvist. Hüpotees pole veel tõestatud.
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 on väljaspool inimvõimet. Paljud matemaatikud tõstatavad küsimuse: kas sellist "programmitõestust" saab pidada kehtivaks tõendiks? Programmis võib ju vigu olla...
Seega jääb vaid loota autorite programmeerimisoskustele ja uskuda, et nad tegid kõik õigesti.
Definitsioon 7.1. Count G= G(V, E) on kahe lõpliku hulga kogum: V – kutsutakse palju tippe ja V elemendipaaride hulk E, st. EÍV´V, kutsus palju servi, kui paarid on järjestamata või palju kaare, kui paarid on järjestatud.
Esimesel juhul graafik G(V, E) helistas orienteerimata, teises - orienteeritud.
NÄIDE. Graaf tippude hulgaga V = (a,b,c) ja servade hulgaga E =((a, b), (b, c))
NÄIDE. Graafik, mille V = (a,b,c,d,e) ja E = ((a, b), (a, e), (b, e), (b, d), (b, c) , (c, d)),
Kui e=(v 1 ,v 2), еОЕ, siis öeldakse, et serv on e ühendab tipud v 1 ja v 2.
Kutsutakse kahte tippu v 1, v 2 külgnevad, kui neid ühendab serv. Sellises olukorras nimetatakse iga tippu intsident vastav serv .
Kaks erinevat ribi külgnevad, kui neil on ühine tipp. Sellises olukorras nimetatakse iga serva juhuslik vastav tipp .
Graafi tippude arv G tähistame v, ja servade arv on e:
.
Graafikute geomeetriline esitus on järgmine:
1) graafi tipp on ruumipunkt (tasapinnal);
2) suunamata graafi serv – segment;
3) suunatud graafiku kaar – suunatud segment.
Definitsioon 7.2. Kui servas e=(v 1 ,v 2) v 1 =v 2 esineb, siis serva e nimetatakse silmus. Kui graafik lubab silmuseid, siis seda nimetatakse graafik silmustega või pseudograaf .
Kui graaf lubab kahe tipu vahel olla rohkem kui üks serv, siis seda nimetatakse multigraaf .
Kui graafi ja/või serva iga tipp on märgistatud, siis kutsutakse sellist graafi märgitud (või laetud ). Tavaliselt kasutatakse märkidena tähti või täisarve.
Definitsioon 7.3. Graafik G (V , E ) helistas alamgraafik (või osa ) graafik G(V,E), Kui V V, E E. Kui V = V, See G helistas hõlmav alamgraaf G.
Näide 7 . 1 . Antud suunamata graafik.
Definitsioon 7.4. Graafikut nimetatakse täielik , Kui ükskõik milline selle kaks tippu on ühendatud servaga. Täielik graafik koos n tipud on tähistatud K n .
Krahvid K 2 , TO 3, TO 4 ja K 5 .
Definitsioon 7.5. Graafik G=G(V, E) kutsutakse kaheiduleheline , Kui V võib kujutada näiteks disjointsete hulkade liiduna V=AB, nii et igal serval on vorm ( v i , v j), Kus v i A Ja v j B.
Iga serv ühendab A-st pärinevat tippu B-st pärineva tipuga, kuid kaht A-st pärit tippu ega B-st kahte tippi ei ole ühendatud.
Kahepoolset graafikut nimetatakse täielik kaheiduleht loendama K m , n, Kui A sisaldab m tipud, B sisaldab n tipud ja iga jaoks v i A, v j B meil on ( v i , v j)E.
Seega kõigile v i A, Ja v j B neid ühendab serv.
K 12 K 23 K 22 K 33
Näide 7 . 2 . Koostage täielik kahepoolne graaf K 2.4 ja täisgraafik K 4 .
Ühiku graafikn- mõõtmetega kuupIN n .
Graafi tipud on n-mõõtmelised kahendhulgad. Servad ühendavad tippe, mis erinevad ühes koordinaadis.
Näide: 
Graafikud on lõbus, rahuldust pakkuv ja hirmutav teema. Graafiteooria – "Tudengi õudus". Graafikalgoritmid on nende avastanud inimeste hämmastavad meeled.
Mis on graafik? Sellele küsimusele oma lugejate jaoks vastamiseks kirjeldan teemat veidi teisiti.
Graafik on objektide kogum.
Enamiku probleemide puhul on tegemist sama tüüpi objektidega. (Paljud linnu või palju maju või palju inimesi või palju muid sama tüüpi asju)
Sellise komplektiga seotud probleemide lahendamiseks peate selle komplekti iga objekti millekski määrama. Üldtunnustatud on nimetada just seda asja graafi tippudeks.
Graafikuid ja põhimääratlusi on mugav kirjeldada piltidega, seega peavad selle lehe lugemiseks olema pildid.
Nagu ma varem kirjutasin, on graafik objektide kogum. Need objektid on tavaliselt sama tüüpi. Lihtsaim viis näidet tuua on linnades. Igaüks meist teab, mis on linn ja mis on tee. Igaüks meist teab, et linna teed võivad olla või mitte. Üldiselt võib mis tahes objektide kogumit iseloomustada graafikuna.
Kui rääkida graafikust kui linnadest, siis linnade vahele saab teed ehitada või kuhugi ära lõhkuda, mitte ehitada või linn asub üldiselt saarel, silda pole ja huvi pakuvad vaid kõvakattega teed. . Vaatamata sellele, et sellisesse linna ei vii ühtegi teed, võib selle linna kaasata paljude analüüsitud objektide hulka ning kõik objektid kokku moodustavad objektide kogumi või lihtsamalt öeldes graafiku.
Kindlasti olete lugenud õpikuid ja näinud seda tähistust G(V,E) või midagi sarnast. Niisiis, V on mingi üks objekt kogu objektide hulgast. Meie puhul on objektide kogumiks linnad, seega on V konkreetne linn. Kuna objektid ei pruugi olla linnad ja sõna objekt võib segadust tekitada, võib sellist komplekti kuuluvat objekti nimetada punktiks, punktiks või millekski muuks, kuid enamasti nimetatakse seda graafi tipuks ja tähistatakse tähega. V.
Programmeerimisel on selleks tavaliselt kahemõõtmelise massiivi veerg või rida, kus massiivi nimetatakse kas naabrusmaatriksiks või esinemismaatriksiks.
Kirjanduses, Internetis ja üldiselt kõikjal, kus graafikute kohta midagi kirjutatakse, kohtate selliseid mõisteid nagu kaared ja servad. Sellel joonisel on kujutatud graafiku servad. Need. need on kolm serva E1, E2 ja E3.
Kaar ja serv erinevad selle poolest, et serv on kahesuunaline ühendus. Ta tahtis seda, ta läks oma naabri juurde, ta tahtis seda, ta tuli naabri juurest tagasi. Kui see pole väga selge, siis võite ette kujutada maja, lennuvälja, lendavat lennukit ja langevarjurit. Langevarjuhüppaja võib minna oma kodust lennuväljale, kuid lennuväljale jõudes meenub talle, et unustas oma õnneliku langevarju koju, naaseb siis koju ja võtab langevarju. — Tee, mida mööda saab edasi-tagasi kõndida, nimetatakse servaks.
Kui langevarjur on lennukis ja hüppab lennukist, kuid langevarjur unustas lennukisse oma õnneliku langevarju selga panna, siis kas langevarjur saab üles korjata selle, mille ta unustas? Teekonda, mis kulgeb ainult ühes suunas, nimetatakse kaareks. Tavaliselt ütleme, et serv ühendab kahte tippu ja kaar läheb ühest tipust teise.
Sellel joonisel on graafikul ainult kaared. Kaared graafikul on tähistatud nooltega, sest ligipääsetav suund on nii selge. Kui graafik koosneb ainult sellistest kaaredest, siis nimetatakse sellist graafikut suunatud.
 |
Sageli puutute kokku külgnevuse ja esinemissageduse mõistetega. Joonisel on punasega märgitud kaks serva, mis lähevad ühte punkti. Selliseid servi, nagu ülalkirjeldatud tippe, nimetatakse ka külgnevateks. |
Palju pole kirjeldatud, kuid see teave võib kedagi aidata.