Nukreiptas grafikas. Nukreipto grafo apibrėžimas Gretumų matricos naudojimo pavyzdys

Briauna yra sutvarkyta viršūnių pora. Vadinamas grafikas, kuriam nurodyta kiekvienos jo briaunos kryptis orientuotas.

Akivaizdu, kad taikymas turnyrams. Pavyzdžiui, rodyklė nuo pralaimėjusios komandos pereina prie laimėjusios, todėl nukreiptame grafike rodomas ne tik kas žaidė, bet ir laimėjo.

Taip pat galite apibrėžti sekimo arba pirmenybės ryšius su nukreiptais grafikais.

Pavyzdžiui, algoritminiuose grafikuose grafiko viršūnės atitinka atliekama operacija, o lankai (orientuotos briaunos) atitinka duomenų priklausomybės(t.y. kokių įvesties duomenų reikia operacijai atlikti).

Pavyzdžiui, atliekant sudėtingą mėginių vertinimą (pavyzdžiui, geologijoje), krašto kryptis rodo pirmenybę. Įprastoje pirmenybės sistemoje ciklų neturėtų būti

Tanya Nataša

kad visada galėtumėte pasirinkti, kitu atveju būtina persvarstyti pirmenybių sistemą.

Vienas kelias.

Kelių žemėlapyje su važiavimo nuorodomis pateikiami specialūs nukreiptų grafikų pavyzdžiai. Norėdami susidoroti su dvipusiais keliais, vietoj vieno kelio (arba vietoj vieno neorientuoto krašto) įvedame dvi orientuotas briaunas, jungiančias tas pačias viršūnes ir turinčias priešingas kryptis.

Kyla klausimas, kokiomis sąlygomis miesto gatvės gali būti orientuotos taip, kad iš bet kurio taško į bet kurį kitą būtų galima judėti nepažeidžiant taisyklių? eismo palei gatves.

Grafų teorijos kalboje jis suformuluotas taip: kokiai sąlygai grafo G briaunos gali būti orientuotos taip, kad bet kuriai jo viršūnių porai būtų jas jungianti orientuota grandinė?

Aišku, kad kiekvienas toks grafikas turi būti sujungtas, bet to nepakanka.

Bus iškviesta briauna E = (A,B). jungiamasis šonkaulis, arba sąsmauka, jei tai vienintelis kelias iš A į B (arba atvirkščiai).

Jungiamoji briauna visas grafo viršūnes padalija į dvi aibes: tas, kurias galima pasiekti iš A, neperžengiant briaunos E, ir tas, kurias galima pasiekti iš B, neperžengiant E. Grafas šiuo atveju susideda iš dviejų dalių G. 1 ir G 2 sujungti tik briauna E (pav. a ir a+1).

Miesto žemėlapyje jungiamasis kraštas yra vienintelis greitkelis, jungiantis atskiras miesto dalis. Aišku, jei tokia greitkelio eismas būtų vienpusis, tai iš vienos miesto dalies į kitą nebūtų pravažiuojama.

Jei briauna E i = (A i, B i) nesijungia, tai yra kitas kelias, jungiantis A i ir B i ir neeinantis išilgai E i. Todėl tokią briauną vadinsime cikline briauna.

2 pav. Įrišimas Fig. 2+1 Galutinis (susiejimas) 2+2 pav. Ciklinis

šonkaulio šonkaulis

1 teorema Jeigu G- nenukreiptas sujungtas grafas, tada visada galima orientuoti ciklines briaunas iš G , paliekant jungiamąsias briaunas nenukreiptas, kad bet kurią šio grafiko viršūnių porą būtų galima sujungti nukreiptu keliu.

Miesto planui šį teiginį galima suformuluoti taip: jei dvipusis eismas paliekamas tik tiltuose (su sąlyga, kad šis tiltas yra vienintelis tiltas per upę) ir akligatviuose, tai visose kitose gatvėse vienpusis eismas. galima sukurti taip, kad transportas užtikrintų susisiekimą su visomis miesto dalimis.

Šią teoremą galime įrodyti nurodydami būdą, kaip tinkamai orientuoti grafą. Rinksimės G savavališkas kraštas E = (A, B) . Jeigu E - jungiamasis kraštas, liks dvipusis, o tada bus galima pajudinti iš A Į IN ir atvirkščiai (2+3 pav.).

pav.2+3 pav. 2+4

Jeigu E yra ciklinis kraštas, tada jis įtraukiamas į kokį nors ciklą SU, ant kurio galite nustatyti ciklinę orientaciją (2+4 pav.).

Tarkime, kad kai kurią dalį jau orientavomės N grafiką G, kad iš bet kurios grafo viršūnės N galite eiti į bet kurią kitą jos viršūnę, laikydamiesi vienpusio eismo taisyklių. Nuo grafiko G yra prijungtas, tada arba N atitinka visą grafiką G, arba yra kraštas E = (A, B), kuriai nepriklauso N , bet viena iš jo viršūnių, tarkim A , priklauso N .

Jeigu E - jungiamoji briauna AB , tada jis išliks dvipusis. Tada bet kuriai viršūnei X grafiką N galite rasti orientuotą grandinę R , jungiantis X su A , o tai reiškia (per kraštą E ), ir su IN . Atgal iš viršaus IN per kraštą E gali eiti į A , o tada išilgai apytikslės grandinės Z - nuo A Į X (a+5 pav.). Tvirtinimas E Į H , jau gausime dauguma grafiką G , turintis reikiamas savybes. Jei kraštas E = (A, B) yra cikliškas, jis priklauso tam tikram ciklui SU . Mes nustatėme kryptį SU iš A prieš IN ir toliau SU iki pirmosios viršūnės D iš SU priklauso N (a+6 pav.).

ryžių. a+5 pav. a+6

Mes pritvirtinsime visus šiuos kraštus N . Leisti X - savavališka viršūnė iš N , A U - bet kuri viršūnė iš SU ; galite rasti orientuotą grandinę R , priklauso N ir jungiantis X Su A , o paskui kartu SU eik į viršų U iš SU . Atgal, iš U galite vaikščioti kartu SU iki viršaus D , o iš jo – priklausymas N orientuota grandinė Z - nuo D Į X . Todėl nukreiptas grafikas, gautas pridedant prie N nurodytos kilpos briaunos SU , taip pat atitinka reikalaujamas sąlygas. Tęsdami šį procesą, galiausiai orientuojame pradinį grafiką reikiamu būdu G .

Viršūnių laipsniai.

Nukreiptiems grafams kiekvienoje viršūnėje turime išeinančių briaunų skaičių p(A) ir įeinančių briaunų skaičių p * (A). Iš viso kraštai yra lygūs:

N = p(A 1) + p(A 2) +... + p(A n) = p * (A 1)+p * (A 2)+...+p * (A n)

Yra Įvairių tipų grafikai, kurių viršūnių laipsniai turi tam tikrų ypatingų savybių. Grafikas vadinamas vienalytis, jei visų jos viršūnių laipsniai lygūs tam pačiam skaičiui r: kiekvienai viršūnei A:

p(A) = p * (A) = r

Pratimas

Sukurkite vienarūšius nukreiptus r = 2 laipsnio grafikus, kurių viršūnių skaičius n = 2,6,7,8.

SANTYKIAI.

Ryšiai ir grafikai.

Bet koks matematinė sistema susijęs su daugybe objektų ar elementų. (Ženklai: algebra, geometrija)

Norint sukurti matematinę teoriją, mums reikia ne tik pačių šių elementų, bet ir santykiai tarp jų. (Pavyzdžiai: skaičiams a > b; geometrijoje - trikampių lygybė, // tiesės; aibių teorijoje - lygybė ir aibių įtraukimas.)

Visi šie santykiai susiję su dviem objektais, todėl jie ir vadinami dvejetainiai santykiai, arba tiesiog santykiai, yra ir kitų santykių tipų, pvz trišaliai santykiai, dėl trijų objektų. (Pavyzdžiui, taškas A yra tarp taškų B ir C).

Pateikiame bendrą dvejetainio ryšio R apibrėžimą: аRв - в yra R santykyje su а.

Pavyzdžiui, santykis a > b reiškia, kad b priklauso visų skaičių, mažesnių už a, aibei

Tiesą sakant, kiekvienas nukreiptas grafikas G apibrėžia tam tikrą ryšį savo viršūnių aibėje. Šį ryšį galima parašyti tokia forma: аGв. Tai reiškia, kad grafas turi nukreiptą briauną, einnčią nuo a iki b.

Specialios sąlygos.

Tegu pateiktas koks nors santykis R. Jei elementas a yra santykyje R su savimi, tai jis atitinka grafiko kilpą

Ryšys R, kurio sąlyga аRв tenkinama bet kokiam a, paskambino atspindintis.

Jei sąlyga аRв netenkinama jokiam elementui, tada iškviečiamas R antirefleksinis požiūris.Šiuo atveju nei viena grafo viršūnė neturi kilpos.

Kiekvienam ryšiui R galime apibrėžti atvirkštinis santykis R*, atsižvelgiant į tai, kad aR * in tada ir tik tada, kai aR in.

Iš atvirkštinio ryšio apibrėžimo aišku, kad jei R atitinkantis grafas G turi briauną (a, b), tai grafas G *, atitinkantis R *, turi turėti briauną (b, a). Kitaip tariant, grafikas G * yra atvirkštinis G, t.y. Grafas su tokiomis pat briaunomis kaip ir G, bet nukreiptas priešingai.

Santykiai vadinami simetriškas, jei aRb reiškia bRa.

Simetrinis ryšys atitinka grafą su nekryptomis briaunomis; ir atvirkščiai, grafas su nenukreiptomis briaunomis apibrėžia tam tikrą simetrinį ryšį.

Santykiai vadinami antisimetriškas, jei iš аRв matyti, kad Rа nevyksta. Antisimetrinių santykių grafikai neturi nekrypčių arba priešingai orientuotų briaunų, jungiančių tą pačią viršūnių porą; be to, ant jų nėra kilpelių, t.y. šie santykiai yra antirefleksiniai.

Santykis tranzityviai, jei iš dviejų sąlygų аRв ir вRс išplaukia, kad аRc.

Tranzityvinio ryšio grafikas turi tokią būdingą savybę: kiekvienai briaunų porai (a, b), (b, c) yra atsilieka kraštas. Pakartotinai taikydami šią savybę, darome išvadą, kad jei šiame grafe yra orientuotas kelias, einantis iš viršūnės X į viršūnę Y, tai yra ir orientuota briauna (x, y).

Tarkime, kad yra grafas G su nukreiptomis briaunomis, kuris nėra tranzityvus. Visais atvejais nukreiptą grafą G galima padaryti pereinamuoju, pridedant prie jo nukreiptų briaunų, kol kiekvienai nuosekliai einančių briaunų porai bus pritvirtintas uždarymas. Taip gautas naujas grafikas G m vadinamas pereinamasis uždarymas G stulpelis.

Ekvivalentiškumo santykiai.

Ekvivalentiškumo santykis, paprastai žymimas simboliu ~, apibūdinamas šiomis trimis savybėmis:

1). Refleksyvumas: a ~ a;

2). Simetrija: nuo a ~ iki Þ iki ~ a;

3). Tranzityvumas: iš a ~ į ir į ~ c Þ a ~ c.

Tiesą sakant, lygiavertiškumo santykis yra lygybės savybės apibendrinimas.

Ekvivalentiškumo santykis įveda skaidinį į viršūnių aibę nevienodos ekvivalentiškumo klasės.

Tegu B i yra lygiavertiškumo grafo G viršūnių aibė, lygiavertė viršūnei i. Tada visos B i priklausančios viršūnės viena su kita sujungiamos briaunomis, t.y. i yra pilnas grafikas G i . Kiekvienoje tokio grafo viršūnėje yra kilpa Grafas G skyla į aibę sujungtų komponentų G i .

Dalinis užsakymas.

Požiūris dalinė tvarka- tai (naudojant rinkinių pavyzdį):

1). Refleksyvumas: A Ê A

2). Tranzityvumas: jei A Ê B ir B Ê C Þ A Ê C

3). Tapatybė: jei A Ê B ir B Ê AÞ A = B

Griežti įtraukimo santykiai -

1). Antirefleksyvumas: ir ÉA niekada nevyksta;

2). Tranzityvumas: jei A É B ir B É C, tai A É C

Užsakymo santykis(griežtąja prasme) vadinamas griežtu įsakymu, a>b, kuriam, be ankstesnių sąlygų, galioja ir:

Išsamumo sąlyga. Bet kokiems dviem nesutampantiems elementams b ir a visada tenkinamas vienas iš dviejų santykių a>b arba b>a.

Paprastai dalinio išdėstymo grafikas vaizduojamas sutvarkyta forma. Kadangi bet kurioms briaunoms (a, b) ir (b, c) yra uždarymo briauna (a, c), ją galima praleisti.

PLOKŠČIAS GRAFIKAS.

Plokštuminių grafikų sąlygos.

Kuratovskio grafikas K 3.3

Trijų namų ir trijų šulinių grafiko uždavinys

Kuratovskio grafas K 5

Šie du grafikai NĖRA PLOKŠTI!

Grafiko išplėtimas- kai kuriuose kraštuose buvo dedamos naujos viršūnės, todėl šios briaunos

tapo elementariomis grandinėmis, susidedančiomis iš kelių briaunų.

Atvirkštinis veikimas, kuriame iš elementariųjų grandinių pašalinamos skiriamosios viršūnės, vadinamas suspaudimas grafiką.

Kuratovskio teorema

Kad grafikas būtų plokščias, būtina ir pakanka, kad jame nebūtų jokio grafo, kurį būtų galima suspausti į grafą K 3, 3 arba grafiką K 5.

EULERO FORMULĖ

Mes apsvarstysime plokštumos grafikus, kurie susidaro plokštumoje daugiakampiai tinklai. Tai reiškia, kad plokštumos grafo G briaunos sudaro vienas šalia kito esančių daugiakampių aibę, dalijančią plokštumą į daugiakampes sritis.

Iš daugiakampių grafikų apibrėžimo matyti, kad jie yra sujungti. Taip pat reikalaujame, kad joks daugiakampis nebūtų kito viduje. Kiekvieno tokio daugiakampio ribinės briaunos sudaro ciklą, kartais vadinamą minimalus ciklas. Plokštumos dalis, esanti daugiakampyje, vadinama grafiko kraštas. Grafike taip pat yra maksimalus ciklas C 1, supančios visumą grafikas su visais jo veidais. Plokštumos dalį, esančią už C 1, taip pat laikysime grafiko paviršiumi su riba C 1 - begalinis veidas F ¥ .

Pažymėkime pagal

viršūnių, briaunų ir paviršių skaičius erdvinis daugiakampis..

Eilerio teorema

c – p + g = 2

Įrodymas: Daugiakampio su n briaunomis formulė akivaizdi. Iš tiesų, n viršūnių ir n briaunų, taip pat du paviršiai F 1 F ¥

Į grafą su r briaunomis pridėkime naują briauną, išilgai veido F ¥ nubrėžkime kokią nors elementarią grandinę, jungiančią dvi maksimalaus grafo G viršūnes. Jei šis lankas turi r briaunų, tai turėsime pridėti r - 1 naują viršūnę ir vieną naujas kraštas. Bet tada

c' - p' + g' = (c + g - 1) - (p + g) + (g + 1) = c - p + g (= 2!)

pagal indukcijos hipotezę.

Matricos reprezentacijos.

1. Incidento matrica A.

A). Nenukreiptam grafikui incidento matrica yra matrica, kurios eilutės atitinka viršūnes, o stulpeliai – briaunas. Matricos elementas yra lygus 1, jei viršūnė patenka į briauną. Kitu atveju matricos elementas įgyja 0 reikšmę.

b). Nukreiptam grafikui kritimo matricos elementas yra +1, kai į lanką krintanti viršūnė yra pradinė lanko viršūnė (t. y. lankas kyla iš šios viršūnės). Elementas yra -1, kai lankas patenka į viršūnę. Jei viršūnė nenukrenta į lanką, tada matricos elementas yra 0.

2. Ciklų matrica C.

A). Nenukreiptam grafikui ciklo matricos eilutės atitinka paprastus grafiko ciklus, o stulpeliai – jo briaunas. Matricos elementas a ij =1, jei cikle C i yra briauna e j . Kitu atveju a ij =0.

b). Nukreiptam grafikui a ij =1, -1 arba 0, priklausomai nuo to, ar ciklo C i ir lanko e j orientacija yra vienoda ar priešinga, ar duotame cikle apskritai nėra lanko e j.

3. Viršūnių gretimų matrica (arba tiesiog gretimų matrica) V yra matrica, kurios eilutės ir stulpeliai atitinka viršūnes, o matricos elementas a ij nekryptinio grafo atveju yra lygus briaunų, jungiančių viršūnes i ir j. Nukreipto grafo elementas a ij yra lygus briaunų, nukreiptų iš viršūnės i į viršūnę j, skaičiui.

Pagrindinės teoremos, susijusios su matricos reprezentacijos grafikai

1).N viršūnių turinčio sujungto grafo (nukreipto ir nenukreipto) dažnio matricos A rangas (maksimalus tiesiškai nepriklausomų stulpelių skaičius) yra lygus (n-1).

2). Sujungto grafo su m briaunų ir n viršūnių ciklo matricos C rangas yra (m-n+1).

Gretimo matricos naudojimo pavyzdys.

Šis žemėlapis rodo, kad grafikai G 1 ir G 2 yra izomorfiniai

Gretimo matricos apima vienalaikį eilučių ir stulpelių permutavimą, kurį galima atlikti naudojant panašumo transformaciją ir permutacijos matricą.

A 2 = PA 1 P", kur

P = , arba p ij =d p(i),j (Kronecker simbolis)

ir P" yra perkelta matrica.

Rasti P matricą gali būti sunku.

G 1 ir G 2 izomorfizmas reiškia, kad A 1 ir A 2 turi tas pačias savąsias reikšmes. Tačiau šios sąlygos nepakanka (pavyzdys žemiau).

Leisti V, D- savavališki rinkiniai ir V??. Pažymėkime pagal V 2 Dekarto kvadrato rinkinys V.

Nukreiptas grafikas arba, trumpai tariant, dviskaita G vadinami trys ( V, D, ts): kur ts- tam tikras aibės D susiejimas su rinkiniu V 2. Rinkinių elementai V Ir D vadinamos atitinkamai dviskaitos viršūnėmis ir lankais G. Digrafo viršūnių ir lankų aibės G jį patogu žymėti VG Ir DG atitinkamai. Jeigu f- tada lankas ts(f) yra sutvarkyta pora ( ir, v), kur Ir : prieš Ј V. Arc f išeina iš viršaus Ir ir eina į viršų v; savo ruožtu Ir Ir v vadinamos galinėmis lanko viršūnėmis f; ateityje rašysime f= (o kartais net - f = uv nebent yra painiavos pavojus).

Rašant savavališką dviženklį, jis paprastai pateikiamas formoje G = (V, D).

Digrafai dažniausiai vaizduojami naudojant diagramas, panašias į grafikų diagramas. Vienintelis skirtumas yra tas, kad linija, vaizduojanti lanką, turi kryptį.

Su kiekvienu dvibalsiu G = (V, D) natūraliai sujungti grafiką G o = (V, E), vadinamas šio dviženklio pagrindu. Norint gauti bazę, būtina dvigrafe G pakeiskite kiekvieną lanką f= kraštas e = uv

Fig. 8 parodytas dviženklis ir jo pagrindas

8 pav

Digrafas G vadinamas prijungtu, jei jo bazė yra prijungta. Orientuotas maršrutas arba, trumpai tariant, arba maršrutas dviženkle G yra kintama viršūnių ir lankų seka

Kuriame

Šis maršrutas paprastai vadinamas (v O , v t) - maršrutas; viršūnės v o Ir v t vadinamos atitinkamai pradine ir galutine tokio maršruto viršūnėmis. Jeigu v o = v t, tada maršrutas vadinamas uždaru. Maršrutą sudarančių lankų skaičius yra maršruto ilgis.

Maršrutas, kuriame nėra pasikartojančių lankų, vadinamas orchain. Paprasta grandinė yra grandinė be pasikartojančių viršūnių (išskyrus, galbūt, sutampančias pradžios ir pabaigos viršūnes). Uždara paprasta grandinė vadinama orciklu arba kontūru.

Nesunku patikrinti, ar egzistuoja (u, v;) - maršrutas garantuoja paprasto ( ir, v) - orcepsas.

Jie sako, kad viršuje v pasiekiamas iš viršaus Ir, jei yra ( ir, v) arba maršrutas. Digrafas G yra stipriai sujungtas arba sujungtas, jei kuri nors jo viršūnė pasiekiama iš bet kurios kitos viršūnės. Akivaizdu, kad yra prijungtas stipriai susijęs dvikalbis; atvirkščiai, žinoma, netiesa.

Grafikas G vadinamas orientuotu, jei jis yra kokio nors stipriai susieto dvigrafo pagrindas.

1.3 teorema. Susietas grafikas G orientuojamės tada ir tik tada, kai kiekviena jo briauna nėra tiltas.

Įrodymas. Tegul grafikas G yra dviskaitos pagrindas N Ir G yra tiltas e. Tada į N yra lankas f=, kur ir, v- šonkaulio galai e. Aišku, į N Ne ( u, v) – maršruto nuorodos. Todėl grafikas G nėra orientuojamasi.

Grįžk, tegul skaičiuoja G neturi tiltų, t.y. kiekvienas grafiko kraštas G yra tam tikrame cikle. Kadangi bet kuris ciklas yra orientuojamasis grafikas, grafike G yra maksimaliai orientuojamas pografas N. Tuo įsitikinkime N = G. Tarkime, kad ši lygybė netenkinama. Dėl grafiko jungties G yra briauna e, kuri patenka į viršūnę v iš N o ne gulėti N. Darant prielaidą, kraštas e yra tam tikrame cikle SU. Pažymėkime pagal K ciklo briaunų rinkinys, nepriklausantis pografui N. Tai nesunku suprasti pridedant N visi kraštai iš komplekto K, vėl gauname orientuojamą pografą, prieštaraujantį pasirinkimui N.

Leisti G- savavališkas dvikalbis. Pusė rezultato laipsnio degv viršūnės v yra visų lankų skaičius v kaip pradžia. Panašiai, pusės laipsnio artėjimas degv yra visų lankų, kurių viršūnė, skaičius v yra pabaiga. Digrafas, kuriame yra P viršūnės ir T lankai mes vadinsime ( n, t) – dviženklis.

Pusė rezultato ir pusės požiūrio laipsniai yra susiję tokiu akivaizdžiu būdu.

1 lema. Leisti G- savavališkas ( n, t) – dviženklis. Tada

Šis teiginys panašus į 1 lemą iš skyriaus. 1,1; ji dažnai vadinama rankos paspaudimo orlema.

Nukreiptas grafikas(trumpai dvikalbis) - (daugia) grafikas, kurio briaunoms priskirta kryptis. Taip pat vadinamos nukreiptos briaunos lankai, o kai kuriuose šaltiniuose tiesiog šonkauliai. Grafas, kuriame nė vienai briaunai nėra priskirta kryptis, vadinamas nenukreiptu grafiku arba ne dvibalsis.

Pagrindinės sąvokos

Formaliai dvigrafas D = (V , E) (\displaystyle D=(V,E)) susideda iš daugelio V (\displaystyle V), kurio elementai vadinami viršūnės, ir rinkiniai E (\displaystyle E) sutvarkytos viršūnių poros u , v ∈ V (\displaystyle u,v\in V).

Arc (u , v) (\displaystyle (u,v)) atsitiktinis viršūnės u (\displaystyle u) Ir v (\displaystyle v). Tuo pačiu jie taip sako u (\displaystyle u) - pradinė viršūnė lankai ir v (\displaystyle v) - galutinė viršūnė.

Ryšys

Maršrutas dvikalbyje yra kintamoji viršūnių seka ir lankas, tipas v 0 ( v 0 , v 1 ) prieš 1 ( v 1 , v 2 ) v 2 . . . v n (\displaystyle v_(0)\(v_(0),v_(1)\)v_(1)\(v_(1),v_(2)\)v_(2)...v_(n))(viršūnės gali kartotis). Maršruto ilgis- lankų skaičius jame.

Kelias Yra maršrutą dvigrafe be pasikartojančių lankų, lengvu keliu- nėra pasikartojančių viršūnių. Jei yra kelias iš vienos viršūnės į kitą, tada antroji viršūnė pasiekiamas nuo pirmos.

Grandinė yra uždaras kelias.

Dėl pusė maršruto panaikinamas lankų krypties apribojimas ir pusiaukelėje Ir pusinės grandinės.

Digrafas labai nuoseklus, arba tiesiog stiprus, jei visos jo viršūnės yra abipusės pasiekiamas; vienpusis prijungimas, arba tiesiog vienašalis, jei iš bet kurių dviejų viršūnių bent viena pasiekiama iš kitos; laisvai sujungti, arba tiesiog silpnas, jei ignoruojant lankų kryptį gaunamas sujungtas (multi)grafas;

Maksimalus stiprus pografas vadinamas stiprus komponentas; vienpusis komponentas Ir silpnas komponentas apibrėžiami panašiai.

Kondensatas dvikalbis D (\displaystyle D) vadinamas digrafu, kurio viršūnės yra stiprieji komponentai D (\displaystyle D), o lankas į D ⋆ (\displaystyle D^(\star )) rodo, kad tarp viršūnių, įtrauktų į atitinkamus komponentus, yra bent vienas lankas.

Papildomi apibrėžimai

Nukreiptas aciklinis grafikas arba hamakas yra nekontūrinis dviženklis.

Vadinamas nukreiptas grafikas, gautas iš duotosios, pakeitus briaunų kryptį į priešingą atvirkščiai.

Visų digrafų su trimis mazgais vaizdas ir savybės

Legenda: SU- silpnas, OS- vienpusis, SS- stiprus, N- yra nukreiptas grafikas, G- yra hamakas (aciklinis), T– tai turnyras

0 lankų	1 lankas	2 lankai	3 lankai	4 lankai	5 lankai	6 lankai
tuščias, N, G	N, G		OS	CC	CC	pilnas, CC
		OS, N, G	CC, N, T	CC
		C, N, G	OS, N, G, T	OS
		C, N, G	OS

Prieš pradėdami tyrinėti pačius algoritmus, turite turėti pagrindinių žinių apie pačius grafikus ir suprasti, kaip jie vaizduojami kompiuteryje. Čia nebus išsamiai aprašyti visi grafų teorijos aspektai (tai nebūtina), o tik tie, kurių nežinojimas labai apsunkins šios programavimo srities įsisavinimą.

Keli pavyzdžiai suteiks nedidelį grafiko eskizą. Taigi tipiškas grafikas yra metro žemėlapis arba koks nors kitas maršrutas. Visų pirma, programuotojas yra susipažinęs su kompiuterių tinklu, kuris taip pat yra grafikas. Čia įprastas dalykas yra taškų, sujungtų linijomis, buvimas. Taigi kompiuterių tinkle taškai yra atskiri serveriai, o linijos – skirtingų tipų elektriniai signalai. Metro pirmiausia yra stotys, antrasis – tarp jų nutiesti tuneliai. Grafų teorijoje taškai vadinami viršūnės (mazgai), o linijos yra šonkauliai (lankai). Taigi, grafiką yra viršūnių, sujungtų briaunomis, rinkinys.

Matematika operuoja ne daiktų turiniu, o jų struktūra, abstrahuojasi nuo visko, kas duota kaip visuma. Naudodami būtent šią techniką galime daryti išvadą, kad kai kurie objektai yra grafikai. Ir kadangi grafų teorija yra matematikos dalis, jai visiškai nesvarbu, kas iš esmės yra objektas; svarbu tik ar tai grafikas, tai yra ar jis turi grafams reikalingas savybes. Todėl prieš pateikdami pavyzdžius nagrinėjamame objekte išryškiname tik tai, kas, mūsų manymu, leis parodyti analogiją, ieškome to, kas bendra.

Grįžkime prie kompiuterių tinklo. Jis turi tam tikrą topologiją ir paprastai gali būti pavaizduotas tam tikro skaičiaus kompiuterių ir juos jungiančių kelių pavidalu. Toliau pateiktame paveikslėlyje kaip pavyzdys parodyta visiškai prijungta topologija.

Iš esmės tai yra grafikas. Penki kompiuteriai yra viršūnės, o jungtys (signalo keliai) tarp jų yra briaunos. Kompiuterius pakeitę viršūnėmis, gauname matematinį objektą – grafą, kuris turi 10 briaunų ir 5 viršūnes. Viršūnės gali būti sunumeruotos bet kokiu būdu ir nebūtinai taip, kaip parodyta paveikslėlyje. Verta paminėti, kad šiame pavyzdyje nenaudojama viena kilpa, tai yra kraštas, kuris palieka viršūnę ir iš karto patenka į ją, tačiau problemose gali atsirasti kilpų.

Štai keletas svarbių žymėjimų, naudojamų grafų teorijoje:

• G=(V, E), čia G yra grafikas, V yra jo viršūnės, o E yra jo briaunos;
• |V| – tvarka (viršūnių skaičius);
• |E| – grafiko dydis (briaunų skaičius).

Mūsų atveju (1 pav.) |V|=5, |E|=10;

Kai bet kuri kita viršūnė pasiekiama iš bet kurios viršūnės, tada toks grafikas vadinamas neorientuotas sujungtas grafikas (1 pav.). Jei grafikas sujungtas, bet ši sąlyga neįvykdyta, tada toks grafikas vadinamas orientuotas arba dviskaita (2 pav.).

Nukreipti ir neorientuoti grafikai turi viršūnės laipsnio sąvoką. Aukščiausias laipsnis yra kraštinių, jungiančių jį su kitomis viršūnėmis, skaičius. Visų grafiko laipsnių suma lygi dvigubam visų jo briaunų skaičiui. 2 paveiksle visų laipsnių suma yra 20.

Dvigrafe, skirtingai nei nekryptiniame grafe, iš viršūnės h į viršūnę s galima pereiti be tarpinių viršūnių, tik tada, kai briauna palieka h ir įeina į s, bet ne atvirkščiai.

Nukreipti grafikai turi tokį žymėjimą:

G=(V, A), kur V – viršūnės, A – nukreiptos briaunos.

Trečiasis grafikų tipas yra sumaišytas grafikus (3 pav.). Jie turi ir nukreiptus, ir nekryptinius kraštus. Formaliai mišrus grafikas rašomas taip: G=(V, E, A), kur kiekviena iš raidžių skliausteliuose reiškia tą patį, kas jam buvo priskirta anksčiau.

3 paveiksle pavaizduotame grafike vieni lankai yra nukreipti [(e, a), (e, c), (a, b), (c, a), (d, b)], kiti – nenukreipti [(e, d), (e, b), (d, c)…].

Iš pirmo žvilgsnio gali atrodyti, kad dviejų ar daugiau grafikų struktūra skiriasi, o tai atsiranda dėl skirtingo jų vaizdavimo. Tačiau taip būna ne visada. Paimkime du grafikus (4 pav.).

Jie yra lygiaverčiai vienas kitam, nes nekeičiant vieno grafo struktūros galima sukurti kitą. Tokie grafikai vadinami izomorfinis, t.y., turinčią savybę, kad bet kuri viršūnė, turinti tam tikrą briaunų skaičių viename grafe, turi identišką viršūnę kitame. 4 paveiksle pavaizduoti du izomorfiniai grafikai.

Kai kiekviena grafiko briauna susieta su tam tikra reikšme, vadinama briaunos svoriu, tada toks grafikas sustabdytas. Atliekant įvairias užduotis, skirtingų tipų matavimai gali veikti kaip svoriai, pavyzdžiui, ilgiai, kainos, maršrutai ir kt. Grafiniame grafike svorio reikšmės paprastai nurodomos šalia kraštų.

Bet kuriame iš mūsų svarstytų grafikų galima pasirinkti kelią ir, be to, daugiau nei vieną. Kelias yra viršūnių seka, kurių kiekviena per briauna yra sujungta su kita. Jei pirmoji ir paskutinė viršūnės sutampa, tai toks kelias vadinamas ciklu. Kelio ilgis nustatomas pagal jį sudarančių kraštų skaičių. Pavyzdžiui, 4.a paveiksle kelias yra seka [(e), (a), (b), (c)]. Šis kelias yra pografas, nes jam taikomas pastarojo apibrėžimas, būtent: grafikas G'=(V', E') yra grafo G=(V, E) pografas tik tada, jei V' ir E' priklauso V, E.

Ankstesniuose skyriuose pateikėme kai kuriuos pagrindinius neorientuotų grafų teorijos rezultatus. Tačiau kai kurioms situacijoms apibūdinti neužtenka neorientuotų grafikų. Pavyzdžiui, vaizduojant eismo modelį kaip grafiką, kurio kraštai atitinka gatves, kraštams turi būti priskirta orientacija, nurodanti leistiną judėjimo kryptį. Kitas pavyzdys yra kompiuterinė programa, modeliuojama grafu, kurio briaunos parodo valdymo srautą iš vienos instrukcijų rinkinio į kitą. Šiame programos vaizde kraštams taip pat reikia priskirti orientaciją, kad būtų nurodyta valdymo srauto kryptis. Kitas fizinės sistemos, kuriai pavaizduoti reikalingas nukreiptas grafikas, pavyzdys yra elektros grandinė. Nukreiptų grafų ir susijusių algoritmų taikymai aptariami skyriuje. 11-15.

Šiame skyriuje pristatomi pagrindiniai nukreiptų grafų teorijos rezultatai. Aptariami klausimai, susiję su orientuotų Eulerio grandinių ir Hamiltono ciklų egzistavimu. Taip pat nagrinėjami orientuoti medžiai ir jų ryšys su orientuotomis Eulerio grandinėmis.

5.1. Pagrindiniai apibrėžimai ir sąvokos

Pradėkime nuo kelių pagrindinių apibrėžimų ir sąvokų, susijusių su nukreiptais grafikais.

Nukreiptas grafikas susideda iš dviejų aibių: baigtinės aibės V, kurios elementai vadinami viršūnėmis, ir baigtinės aibės E, kurios elementai vadinami briaunomis arba lankais. Kiekvienas lankas yra susietas su sutvarkyta viršūnių pora.

Simboliai naudojami viršūnėms žymėti, o simboliai – lankams. Jei , tada jie vadinami galinėmis viršūnėmis; šiuo atveju - pradinė viršūnė, - galutinė viršūnė. Visi lankai, turintys vieną pradžios ir pabaigos viršūnių porą, vadinami lygiagrečiais. Lankas vadinamas kilpa, jei krintanti viršūnė yra ir pradinė, ir galutinė.

Grafiniame nukreipto grafiko vaizde viršūnės vaizduojamos kaip taškai arba apskritimai, o kraštai (lankai) vaizduojami kaip segmentai

linijos, jungiančios taškus arba apskritimus, vaizduojančius jų galines viršūnes. Be to, lankams priskiriama orientacija, kurią rodo rodyklė, nukreipta nuo pradžios viršūnės iki pabaigos viršūnės.

Pavyzdžiui, jei jų), nukreiptas grafikas gali būti pavaizduotas Fig. 5.1. Šiame grafike yra lygiagrečių lankų, o a yra kilpa.

Ryžiai. 5.1. Nukreiptas grafikas.

Sakoma, kad lankas patenka į jo galines viršūnes. Viršūnės vadinamos gretimomis, jei jos yra vieno lanko galiniai taškai. Jei lankai turi bendrą galinę viršūnę, tada jie vadinami gretimais.

Sakoma, kad lankas prasideda nuo pradinės viršūnės ir baigiasi galutinėje viršūnėje. Viršūnė vadinama izoliuota, jei ji neturi kritimo lankų.

Viršūnės laipsnis yra į ją krentančių lankų skaičius. Viršūnės įėjimo pusė laipsnio yra lankų, įeinančių į V], skaičius, o ištekėjimo pusė – iš jos sklindančių lankų skaičius. Simboliai ir b" žymi minimalų nukreipto grafiko išėjimo ir įėjimo pusę laipsnio. Panašiai simboliai žymi atitinkamai didžiausią išeinančio ir įėjimo pusę laipsnio.

Bet kurios viršūnės aibės apibrėžiamos taip: . Pavyzdžiui, grafike pav. 5.1.

Atkreipkite dėmesį, kad kilpa padidina tiek įėjimo, tiek išėjimo iš šios viršūnės pusę laipsnio. Šis teiginys yra to fakto, kad kiekvienas lankas padidina 1 nukreipto grafiko įėjimo ir išėjimo pusės laipsnių sumą.

5.1 teorema. Nukreiptame grafike su lankais

Įėjimo pusės laipsnių suma = pusės išėjimo laipsnių suma = m.

Nukreipto grafo pografai ir generuojami pografai apibrėžiami taip pat, kaip ir nekryptinių grafų atveju (1.2 skyrius).

Nenukreiptas grafikas, atsirandantis dėl nukreipto grafo G lankų deorientacijos, vadinamas pagrindiniu nekryptiniu grafiku G ir žymimas .

Nukreipto grafo kryptingas maršrutas yra tokia baigtinė viršūnių seka

Kas yra grafo G lankas. Toks maršrutas paprastai vadinamas nukreiptu -maršrutu, kurio pradinė viršūnė yra maršruto pabaigos viršūnė, o visos kitos viršūnės yra vidinės. Nukreipto maršruto pradžios ir pabaigos viršūnės vadinamos jo galinėmis viršūnėmis. Atkreipkite dėmesį, kad nukreiptame maršrute lankai, taigi ir viršūnės, gali atsirasti daugiau nei vieną kartą.

Orientuotas maršrutas vadinamas atviru, jei jo galinės viršūnės skiriasi, kitu atveju jis vadinamas uždaru.

Orientuotas maršrutas vadinamas orientuota grandine, jei visi jo lankai yra skirtingi. Orientuota grandinė yra atvira, jei jos galinės viršūnės skiriasi, kitu atveju ji yra uždara.

Atviras orientuotas kelias vadinamas orientuotu keliu, jei visos jo viršūnės yra skirtingos.

Uždara orientuota grandinė vadinama orientuotu ciklu arba kontūru, jei jos viršūnės, išskyrus galines, yra skirtingos.

Nukreiptas grafikas yra aciklinis arba bekontūrinis, jei jis neturi kontūrų. Pavyzdžiui, nukreiptas grafikas pav. yra aciklinis. 5.2.

Ryžiai. 5.2. Aciklinis nukreiptas grafikas.

Ryžiai. 5.3. Stipriai sujungtas nukreiptas grafikas.

Viršūnių seka nukreiptame grafe G vadinama maršrutu G, jei tai yra maršrutas pagrindiniame nenukreiptame grafe. Pavyzdžiui, seka grafe Fig. 5.2 yra maršrutas, bet ne orientuotas.

Panašiai apibrėžiami ir nukreipto grafiko grandinė, kelias ir ciklas.

Nukreiptas grafikas vadinamas sujungtu, jei yra prijungtas pagrindinis neorientuotas grafikas.

Kryptingo grafo G pografas vadinamas G komponentu, jei jis yra grafo komponentas

Sakoma, kad nukreipto grafo G viršūnės yra stipriai susijusios, jei yra nukreipti keliai iš ir į G. Jei jis yra stipriai susijęs su tada, akivaizdu, kad jis yra stipriai susijęs su . Kiekviena viršūnė yra stipriai susijusi su savimi.

Jei viršūnė yra stipriai sujungta su viršūne, tai, kaip nesunku pastebėti, viršūnė yra stipriai sujungta su viršūne, todėl šiuo atveju tiesiog sakome, kad viršūnės yra stipriai sujungtos.

Nukreiptas grafikas vadinamas stipriai sujungtu, jei visos jo viršūnės yra stipriai sujungtos. Pavyzdžiui, grafikas pav. yra stipriai susijęs. 5.3.

Maksimalus stipriai sujungtas kryptingo grafo G pografas vadinamas stipriai sujungtu G komponentu. Jei nukreiptas grafikas yra stipriai sujungtas, tai jis turi vieną stipriai susietą komponentą, būtent save patį.

Apsvarstykite nukreiptą grafiką. Nesunku pastebėti, kad kiekviena jos viršūnė priklauso tiksliai vienai stipriai susijusiai grafo G komponentei. Vadinasi, stipriai sujungtų komponentų viršūnių aibės sudaro grafo viršūnių aibės Y skaidinį.

Ryžiai. 5.4. Grafas ir jo kondensacija.

Pavyzdžiui, nukreiptas grafikas pav. 5.4, ​​bet turi tris stipriai sujungtus komponentus su viršūnių rinkiniais ir sudarančius nukreipto grafo viršūnių aibės skaidinį.

Įdomu tai, kad nukreiptame grafe gali būti lankų, kurie nėra įtraukti į jokius stipriai sujungtus grafo komponentus. Pavyzdžiui, jokiuose stipriai sujungtuose komponentuose nėra jokių lankų grafike 1 pav. 5.4, ​​a.

Taigi, nors „stipraus jungiamumo“ savybė apima grafo viršūnių aibės padalijimą, dėl to lankų aibė gali būti skaidoma.

Sąjunga, sankirta, suma mod 2 ir kitos kryptingų grafų operacijos apibrėžiamos lygiai taip pat, kaip ir nenukreiptų grafų atveju (1.5 skyrius).

Grafas, gautas sutraukus visus stipriai sujungtų kryptingo grafo G komponentų lankus, vadinamas sutankintuoju G grafiku. Grafo, parodyto pav., kondensacija. 5.4, ​​a, parodyta fig. 5.4, ​​b.

Grafo viršūnės atitinka stipriai susietas grafo G komponentes ir yra vadinamos sutirštėjusiais komponentų vaizdais.

Nukreipto grafo rangas ir ciklomatinis skaičius yra tokie patys kaip ir atitinkamo nekryptivo grafo. Tai reiškia, kad jei nukreiptas grafikas G turi lankus, viršūnes ir komponentus, tada grafo G rangą ir ciklomatinį skaičių nustato išraiškos

Dabar apibrėžkime minimaliai sujungtus nukreiptus grafikus ir išnagrinėkime kai kurias jų savybes.

Nukreiptas grafikas G vadinamas minimaliai sujungtu, jei jis yra stipriai sujungtas, o pašalinus bet kokį lanką, jis netenka stipriai sujungtos savybės.

Ryžiai. 5.5. Minimaliai sujungtas nukreiptas grafikas.

Pavyzdžiui, grafikas, parodytas 1 pav., yra minimaliai sujungtas. 5.5.

Akivaizdu, kad minimaliai sujungti grafikai negali turėti lygiagrečių lankų ir kilpų.

Žinome, kad neorientuotas grafikas yra minimaliai sujungtas tada ir tik tada, kai jis yra medis (2.13 pavyzdys). Remiantis 2.5 teorema, medis turi bent dvi 1 laipsnio viršūnes. Todėl minimaliai sujungti neorientuoti grafikai turi bent dvi 1 laipsnio viršūnes.

Nustatykime panašų rezultatą nukreiptiems grafams. Kiekvienos stipriai sujungto nukreipto grafo viršūnės laipsnis turi būti ne mažesnis kaip 2, nes kiekviena viršūnė turi turėti išeinantį ir įeinantį lanką. Kitoje teoremoje įrodome, kad minimaliai sujungtas nukreiptas grafikas turi bent dvi 2 laipsnio viršūnes.