Analogiškai su pasiekiamumo grafiku apibrėžiame stiprią pasiekiamumo grafiką.

Apibrėžimas: Tegul yra nukreiptas grafikas. Stiprus pasiekiamumo grafikas
Už taip pat turi daug viršūnių ir kitas kraštų rinkinys
stulpelyje viršūnės Ir abipusiai prieinami.

Remiantis pasiekiamumo grafiko matrica
lengva sukurti matricą
stiprus pasiekiamumo grafikas. Iš tiesų, iš pasiekiamumo ir stipraus pasiekiamumo apibrėžimų iš karto matyti, kad visos poros
,
, elemento vertė
lygus 1 tada ir tik tada, kai abu elementai
Ir
yra lygūs 1, t.y.

Pagal matricą
galima nustatyti stipriai sujungto grafo komponentus taip:

Kartojame antrą veiksmą, kol visos viršūnės bus paskirstytos tarp komponentų.

Mūsų diagramos pavyzdyje 14.1 pavyzdys. pagal matricą
gauname tokią stipraus pasiekiamumo grafiko matricą

Naudodami aukščiau aprašytą procedūrą, nustatome, kad grafiko viršūnės yra suskirstyti į 4 stipraus ryšio komponentus:
,
,
,
. Tvirtai susijusių komponentų rinkinyje taip pat apibrėžiame pasiekiamumo ryšį.

Apibrėžimas: Leiskite
Ir
– stipriai sujungti grafiko komponentai . Komponentas
pasiekiamas iš komponentų
, Jei
arba yra dvi tokios viršūnės
Ir
, Ką pasiekiamas iš .
griežtai pasiekiamas nuo
, Jei
Ir
pasiekiamas iš
. Komponentas
vadinamas minimaliu, jei jis nėra griežtai pasiekiamas iš jokio komponento.

Kadangi visos vieno komponento viršūnės yra abipusiai pasiekiamos, nesunku suprasti, kad pasiekiamumo ir griežto pasiekiamumo santykiai komponentuose nepriklauso nuo viršūnių pasirinkimo.
Ir
.

Iš apibrėžimo nesunkiai išvedama tokia griežto pasiekiamumo savybė.

Lemma: Griežtas pasiekiamumo santykis – tai dalinės tvarkos santykis, t.y. jis yra antirefleksinis, antisimetriškas ir tranzityvus.

Šis ryšys gali būti pavaizduotas kaip nukreiptas grafikas, kurio viršūnės yra komponentai ir briauna
reiškia tai
griežtai pasiekiamas nuo
. Žemiau pateikiamas 14.1 pavyzdyje pateikto grafiko komponentų grafikas.

Šiuo atveju yra vienas minimalus komponentas
.

Daugelyje programų nukreiptas grafikas vaizduoja tam tikrų išteklių paskirstymo tinklą: produktą, prekes, informaciją ir kt. Tokiais atvejais natūraliai iškyla užduotis surasti minimalų skaičių tokių taškų (viršūnių), iš kurių šis resursas gali būti pristatytas į bet kurį tinklo tašką.

Apibrėžimas: Leiskite
- nukreiptas grafikas. Viršūnių poaibis
paskambino generuojantys, jei iš viršūnių
galite pasiekti bet kurią grafiko viršūnę. Viršūnių poaibis
vadinamas grafiko pagrindu, jei jis generuoja, bet joks tinkamas jo poaibis negeneruoja.

Ši teorema leidžia efektyviai rasti visas grafo bazes.

Teorema: Leiskite
- nukreiptas grafikas. Viršūnių poaibis
yra pagrindas jei ir tik tada, kai yra viena viršūnė iš kiekvieno minimaliai stipriai sujungto komponento ir neturi jokių kitų viršūnių.

Įrodymas: Pirmiausia atkreipkime dėmesį, kad kiekviena grafo viršūnė pasiekiama iš viršūnės, priklausančios kokiam nors minimaliam komponentui. Todėl viršūnių aibė
, turintis vieną viršūnę iš kiekvieno minimalaus komponento, generuoja, o kai iš jos pašalinama bet kuri viršūnė, ji nustoja tokia būti, nes viršūnės iš atitinkamo minimalaus komponento tampa nepasiekiamos. Štai kodėl
yra pagrindas.

Atgal, jei
yra pagrindas, tada joje turi būti bent viena viršūnė iš kiekvieno minimalaus komponento, kitaip tokio minimalaus komponento viršūnės bus nepasiekiamos. Jokių kitų viršūnių
negali būti, nes kiekviena iš jų pasiekiama iš jau įtrauktų viršūnių.

Iš šios teoremos seka tokia vieno grafiko sudarymo arba visų grafiko bazių surašymo procedūra :

14.3 pavyzdys: Apibrėžkime visas nukreipto grafiko bazes .

Pirmajame etape randame stipraus ryšio komponentus :

Antrame etape sudarome griežtą šių komponentų pasiekiamumo grafiką.

Mes nustatome minimalius komponentus:
,
Ir
.

Galiausiai išvardijame visas keturias bazes :
,
,
Ir
.

Nagrinėjami digrafų pasiekiamumo klausimai ir pasiekiamumo bei priešpriešinio pasiekiamumo matricų radimo metodai. Mes svarstome matricos metodą, skirtą kelių tarp bet kurių grafo viršūnių skaičiui rasti, taip pat viršūnių, įtrauktų į kelią tarp viršūnių poros, rinkinį. Paskaitos tikslas: Suteikti supratimą apie pasiekiamumą ir priešpriešinį pasiekiamumą bei kaip juos rasti

Pasiekiamumas ir priešpriešinis pasiekiamumas

Užduotys, kuriose vartojama sąvoka pasiekiamumas, gana daug.

Štai vienas iš jų. Grafikas gali būti tam tikros organizacijos modelis, kuriame žmones reprezentuoja viršūnės, o lankai interpretuoja komunikacijos kanalus. Nagrinėjant tokį modelį, galima kelti klausimą, ar informacija iš vieno asmens i gali būti perduota kitam asmeniui j, tai yra, ar yra kelias, einantis iš viršūnių i į viršūnes j. Jei toks kelias egzistuoja, tada jie sako, kad viršūnės j pasiekiamas iš viršūnių i. Galima domėtis viršūnių j pasiekiamumu iš viršūnių i tik tuose keliuose, kurių ilgis neviršija nurodytos reikšmės arba kurių ilgis yra mažesnis didžiausias skaičius viršūnių grafe ir kt.

Pasiekiamumas grafike apibūdinamas pasiekiamumo matrica R=, i, j=1, 2, ... n, kur n yra grafiko viršūnių skaičius, o kiekvienas elementas apibrėžiamas taip:

r ij =1, jei viršūnės j pasiekiamos iš x i,

r ij = 0, kitaip.

Grafo G viršūnių aibė R(x i), pasiekiama iš duotosios viršūnės x i, susideda iš tų elementų x i, kurių pasiekiamumo matricoje (i, j)-tasis elementas yra lygus 1. Akivaizdu, kad visos įstrižainės Matricos R elementai yra lygūs 1, nes kiekviena viršūnė pasiekiama iš savęs 0 ilgio keliu. Kadangi tiesioginis 1 eilės atvaizdavimas Г +1 (x i) yra viršūnių x j, kurios pasiekiamos iš x i, aibė 1 ilgio takai, tada aibė Г + (Г +1 (x i)) = Г +2 (x i)susideda iš viršūnių, kurias galima pasiekti iš x i naudojant 2 ilgio takus. Panašiai +p (x i) yra aibė viršūnių, kurias galima pasiekti iš x i naudojant p ilgio takus.

Kadangi bet kuri grafo viršūnė, kurią galima pasiekti iš x i, turi būti pasiekiama naudojant 0 arba 1, arba 2, ... arba p ilgio kelią (ar kelius), tada viršūnių rinkinys, pasiekiamas viršūnei x i, gali būti pavaizduotas kaip

R (x i) = ( x i ) Г +1 (x i) Г +2 (x i) ...Г +p (x i).

Kaip matome, pasiekiamų viršūnių aibė R(x i) yra tiesioginis tranzityvus viršūnės x i uždarymas, ty R(x i) = T + (x i). Taigi, norėdami sudaryti pasiekiamumo matricą, randame pasiekiamas aibes R(x i) visoms viršūnėms x i X. Darant prielaidą, kad r ij =1, jei x j R(x i) ir r ij =0 kitu atveju.

Ryžiai. 4.1. Pasiekiamumas grafike: a –grafas; b – gretimų matrica; c – pasiekiamumo matrica; r yra priešingo pasiekiamumo matrica.

Grafikui, parodytam pav. 4.1,a, pasiekiamumo rinkinys randami taip:

R (x 1) = (x 1) (x 2, x 5) (x 2, x 4, x 5) (x 2, x 4, x 5) = (x 1, x 2, x 4, x 5) ),

R(x2) = (x2)(x2, x4)(x2, x4, x5)(x2, x4, x5) = (x2, x4, x5),

R(x3) = (x3)(x4)(x5)(x5) = (x3, x4, x5),

R(x4) = (x4)(x5)(x5) = (x4, x5),

R(x5) = (x5)(x5) = (x5),

R(x6) = (x6)(x3, x7)(x4, x6)(x3, x5, x7)(x4, x5, x6) = (x3, x 4, x 5, x 6, x 7),

R(x7) = (x7)(x4, x6)(x3, x5, x7)(x4, x5, x6) = (x3, x4, x5, x6, x 7).

Pasiekiamumo matrica atrodo kaip parodyta pav. 4.1,c. Pasiekiamumo matrica galima statyti pagal gretimų matrica(4.1 pav., b), sudarydami aibes T + (x i) kiekvienai viršūnei x i.

Priešpriešinio pasiekiamumo matrica Q = [ q ij ],i, j =1, 2, ... n, kur n yra grafo viršūnių skaičius, apibrėžiamas taip:

q ij =1, jei iš viršūnės x j galima pasiekti viršūnę x i,

q ij = 0, kitaip.

Priešpriešinis pasiekiamas aibėQ (x i) yra tokia viršūnių aibė, kad iš bet kurios šios aibės viršūnės galima pasiekti viršūnę x i. Panašiai kaip sudarydami pasiekiamą aibę R (x i), galime parašyti Q (x i) išraišką:

Q (x i) = ( x i ) Г -1 (x i) Г - 2(x i) ...Г -p (x i).

Taigi aišku, kad Q (x i) yra ne kas kita, kaip atvirkštinis tranzityvus viršūnės x i uždarymas, t.y. Q (x i) = T - (x i). Iš apibrėžimų akivaizdu, kad Q matricos stulpelis x i (kuriame q ij =1, jei x j Q (x i), o q ij =0 kitaip) sutampa su matricos R eilute x i, ty Q = R T , kur R T yra matrica perkelta į pasiekiamumo matrica R.

Priešpriešinio pasiekiamumo matrica parodyta pav. 4,1, g.

Pažymėtina, kad kadangi visi R ir Q matricų elementai yra lygūs 1 arba 0, kiekviena eilutė gali būti saugoma dvejetaine forma, taupant kompiuterio atminties sąnaudas. Matricos R ir Q yra patogios kompiuteriniam apdorojimui, nes skaičiavimo požiūriu pagrindinės operacijos yra didelės spartos loginės operacijos.

Į kelią įtrauktų viršūnių aibės radimas

Jei jums reikia žinoti apie šiuose keliuose esančias grafiko viršūnes, turėtumėte prisiminti tiesioginio ir atvirkštinio tranzityvaus uždarymo apibrėžimus. Kadangi T + (x i) yra aibė viršūnių, į kurias yra keliai iš viršūnės x i, o T – (x j) yra viršūnių, iš kurių yra keliai į x j, aibė, tada T + (x i) T – (x j) yra viršūnių aibė , kurių kiekviena priklauso bent vienam keliui , einančiam nuo x i iki x j . Šios viršūnės vadinamos esminėmis arba integralinėmis dviejų galinių viršūnių x i ir x j atžvilgiu. Visos kitos grafo viršūnės vadinamos nereikšmingomis arba perteklinėmis, nes jų pašalinimas neturi įtakos keliams nuo x i iki x j.

Ryžiai. 4.2. Digrafas

Taigi diagramoje pav. 4.2, ieškant į kelią įtrauktų viršūnių, pavyzdžiui, nuo viršūnės x 2 iki viršūnių 4, reikia rasti T + (x 2) = (x 2, x 3, x 4, x 5, x 6),

T – (x 4) =( x 1, x 2, x 3, x 4, x 5) ir jų sankirtos T + (x 2) T – (x 4) =( x 2, x 3, x 4, x 5).

Matricos metodas kelių radimas grafikuose

Gretimumo matrica visiškai lemia grafiko struktūrą. Padėkime gretumo matricą kvadratu pagal matematikos taisykles. Kiekvienas matricos A 2 elementas nustatomas pagal formulę

a (2) ik = n j=1 a ij a jk

Terminas formulėje yra lygus 1 tada ir tik tada, kai abu skaičiai a ij ir a jk yra lygūs 1, kitu atveju jis yra lygus 0. Kadangi lygybė a ij = a jk = 1 reiškia ilgio kelio egzistavimą 2 nuo viršūnės x i iki viršūnių k, einančių per viršūnę x j , tada (i-tas, k-tas) matricos A 2 elementas lygus skaičiui 2 ilgio takai iš x i į k .

4.1a lentelėje parodyta grafiko gretimumo matrica, parodyta pav. 4.2. Gretimo matricos A 2 kvadratūros rezultatas parodytas 4.1b lentelėje.

Taigi „1“, stovinti antrosios eilutės ir ketvirto stulpelio sankirtoje, rodo vieno 2 ilgio kelio egzistavimą nuo viršūnės x 2 iki viršūnių 4. Iš tiesų, kaip matome grafiką pav. 4.2, yra toks kelias: a 6 , a 5 . „2“ matricoje A 2 rodo, kad yra du 2 ilgio takai nuo 3 viršūnių iki 6 viršūnių: a 8, a 4 ir 10, a 3.

Panašiai gretumo matricai, padidintai iki trečiosios laipsnio A 3 (4.1c lentelė), a (3) ik yra lygus 3 ilgio takų, einančių iš x i kx k, skaičiui. Iš ketvirtos matricos A 3 eilutės aišku, kad yra 3 ilgio takai: vienas iš 4 iš 4 (a 9, a 8, a 5), ​​vienas iš 4 į

x 5 (a 9, a 10, a 6) ir du keliai nuo x 4 iki 6 (a 9, a 10, a 3 ir a 9, a 8, a 4). Matrica A 4 rodo 4 ilgio takų egzistavimą (4.1d lentelė).

Taigi, jei p ik yra matricos A p elementas, tai p ik yra lygus takų (nebūtinai orgrandinių ar paprastų grandinių), kurių ilgis p einantis iš x i kx k, skaičiui.

PASIEKIAMUMAS IR SUSIJUNGIMAS GRAFUOSE Paskaitos planas: Trasų maršrutai ir ciklai. Grafinis ryšys ir prijungti komponentai. Diagramos skersmens spindulys ir centras.

Pasidalinkite savo darbais socialiniuose tinkluose

Jei šis darbas jums netinka, puslapio apačioje yra panašių darbų sąrašas. Taip pat galite naudoti paieškos mygtuką

Baranovas Viktoras Pavlovičius. Diskretioji matematika. 3 skyrius.Grafikai, tinklai, kodai.

8 paskaita. Pasiekiamumas ir jungiamumas grafikuose

8 paskaita. PASIEKIAMUMAS IR SUJUNGIMAS GRAFUOSE

Paskaitos metmenys:

1. Maršrutai, grandinės ir ciklai.
2. Grafinis ryšys ir prijungti komponentai.
3. Diagramos skersmuo, spindulys ir centras.
4. Pasiekiamumo ir priešpriešinio pasiekiamumo matricos.

1. Maršrutai, grandinės ir kilpos

Nukreiptas maršrutas(arba pagal ) yra lankų seka, kurioje bet kurio lanko, kuris skiriasi nuo paskutinės, galutinė viršūnė yra kitos lanko pradinė viršūnė. Fig. 1 lanko sekos

, (1)

, (2)

(3)

yra keliai.

Ryžiai. 1.

Orientuotas į grandinę(arba grandinė ) yra kelias, kuriame kiekvienas lankas ir Su Naudotas ne daugiau kaip vieną kartą. Taigi, pavyzdžiui, takai (2) ir (3) yra orcepsai, o kelias (1) nėra, nes lankas jame naudojamas du kartus.

Paprasta vadinama grandine, kurioje kiekviena viršūnė naudojama daugiausia vieną kartą O ą kartą. Pavyzdžiui, grandinė (3) yra paprasta, bet grandinė (2) ne.

Maršrutas yra nenukreiptas kelio dvigubas, tai yra briaunų seka, kurioje kiekviena briauna, išskyrus pirmą ir paskutinę, galinėmis viršūnėmis sujungta su briaunomis ir. Virš lanko simbolio esanti juosta reiškia, kad ji traktuojama kaip briauna.

Taip pat, kaip apibrėžėme grandines ir paprastas grandines, galime apibrėžti grandines ir paprastas grandines.

Kelias arba maršrutas taip pat gali būti pavaizduoti kaip viršūnių seka. Pavyzdžiui Ir priemonės, kelias (1) gali būti parašytas taip: .

Kelias vadinamas uždaru , jei pradinė lanko viršūnė sutampa su pabaiga h nauja lanko viršūnė. Vadinamos uždaros grandinės (grandinės). arbaciklai (ciklai ). Orciklai taip pat vadinami kontūrai . Vadinamos uždaros paprastos grandinės (grandinės). yra paprasti orciklai(ciklais). Uždarytas maršrutasyra neorientuotas n ny dvynys uždaro p ties ty.

1. Grafinis ryšys ir prijungti komponentai

Sakoma, kad dviženklio viršūnė pasiekiama iš viršūnės, jei yra kelias. Jei tuo pačiu metu iš yra pasiekiamas, tada šios viršūnės yra tarpusavyje pasiekiamos.

Digrafas vadinamas stipriai sujungtu arba stipriu , jei jame yra kurios nors dvi viršūnės A yra pasiekiami. Stipraus digrafo pavyzdys parodytas fig. 2 a. Kadangi stulpelyje jie e Jei yra orciklas, apimantis visas viršūnes, tada bet kurios dvi iš jų ir jie yra pasiekiami.

° ° °

° ° ° ° ° °

° ° ° ° ° °

a b c

Ryžiai. 2.

Digrafas vadinamasvienpusis prijungimas arba vienpusis , jei bet kurioje jos viršūnių poroje bent viena yra pasiekiama iš kitos. Vienpusio grafiko pavyzdys parodytas fig. 2 b. Šis grafikas turi orciklą, kuriame yra keturios abipusiai prieinamos viršūnės. Viršūnė turi nulinį artėjimo laipsnį, o tai reiškia, kad nėra kelių, vedančių į šią viršūnę. Šiuo atveju pasiekiama bet kuri iš keturių likusių viršūnių.

Digrafas vadinamas silpnai prijungtas arba silpnas , jei jame yra bet kurios dvi viršūnės su o susivienijo pusiaukelėje . Pusė kelio, skirtingai nei kelias, gali turėti priešingą kryptį V linijos lankai. Silpno digrafo pavyzdys parodytas fig. 2-asis amžius Akivaizdu, kad grafike nėra n adresu tarp viršūnių ir, bet yra pusiaukelė, susidedanti iš priešingos n A ištiesinti lankai ir kt.

Jei kai kuriai viršūnių porai nėra maršruto, jungiančio jas, tada A kaip vadinamas dvibalsis nenuoseklus.

Dvigubai apibrėžiami trys sujungtų komponentų tipai:stiprus komponentas ma k stipriausias pografas,vienpusis komponentasmaksimalus vienvietis O Ronny pografas irsilpnas komponentassilpniausias pografas.

Stipraus komponento sąvoka parodyta fig. 3.

° ° ° ° ° °

° ° ° °

° ° ° ° ° °

° ° ° ° ° °

° ° °

° ° ° ° °

Ryžiai. 3

Grafike, kuris yra sujungtas viena kryptimi, yra šeši stiprūs d grafikai, kurių tik stiprieji komponentai n tami. Panašiai iliustruojama ir vienpusio komponento sąvoka. Šioje pastaboje e Vienpusis komponentas sutampa su pačiu grafiku. Jei pakeisite orientaciją A lanko sujungimas, pavyzdžiui, priešingas, gauname silpną grafiką su dviem vieno taško O ronaliniai komponentai, kurių vieną sudaro viršūnės, o kitą – viršūnės r padangos.

Nenukreiptam grafikui jo viršūnių aibėje apibrėžiame dėžę r narrys ryšys, darant prielaidą, kad yra grandinė, jungianti su. Toks yra regiono požiūris A suteikia refleksyvumo, simetrijos ir tranzityvumo savybes, tai yra apie T nešiojimo lygiavertiškumas. Jis padalija viršūnių rinkinį į nejungtas klases: . Dvi viršūnės iš tos pačios klasės yra lygiavertės, tai yra, grafas turi jas jungiančią grandinę skirtingų klasių viršūnėms tokios grandinės nėra. Kadangi galai yra l yu Jei briaunos yra santykyje, tai grafo briaunų aibė taip pat bus padalinta į disjunktines klases: , kur per žymi aibę visų briaunų, kurių galai priklauso, .

Grafikai yra sujungti ir sudaro grafiką. Šie grafikai vadinamiryšio komponentaigrafiką. Skaičius yra dar viena skaitinė grafiko charakteristika. Sujungtam grafikui, jei grafikas yra atjungtas, tada.

Jei duotas grafikas nėra sujungtas ir suskaidomas į keletą komponentų, bet kurio klausimo, susijusio su šiuo grafiku, sprendimas, kaip taisyklė, gali būti sumažintas iki atskirų sujungtų komponentų tyrimo. Todėl daugeliu atvejų prasminga manyti, kad pateiktas grafikas yra sujungtas.

1. Diagramos skersmuo, spindulys ir centras

Sujungtam grafikui apibrėžiame atstumas tarp dviejų jo viršūnių ir kaip trumpiausios grandinės, jungiančios šias viršūnes, ilgis ir žymimas. Grandinės ilgis yra kraštų, sudarančių grandinę, skaičius. Nesunku patikrinti, ką įvedėte. n Šis atstumas atitinka metrikos aksiomas:

2) ;

3) .

Nustatykime atstumą nuo kiekvienos grafo viršūnės iki tolimiausios nuo jos viršūnės

kuris vadinamasekscentriškumas. Akivaizdu, kad ekscentriškumas visoms viso grafo viršūnėms yra lygus vienetui, o paprasto ciklo viršūnių – .

Didžiausias ekscentriškumas vadinamas skersmuo grafiką ir minimumą spindulys grafiką. Visame grafike turime, o paprastame cikle .

Viršūnė vadinama centrine, jei. Grafike gali būti keletas b į tokias viršūnes, o kai kuriuose grafikuose visos viršūnės yra centrinės. Paprastoje grandinėje su nelyginiu viršūnių skaičiumi tik viena yra centrinė, o su lyginiu skaičiumi, Su Yra dvi tokios viršūnės. Visame grafe ir paprastame cikle visos viršūnės yra centrinės. Centrinių viršūnių aibė vadinama grafiko centras.

1 pavyzdys. Raskite grafiko skersmenį, spindulį ir centrą, parodytą pav. 4.

° °

° ° °

° °

° °

Ryžiai. 4.

Norint išspręsti šią problemą, patogu iš anksto apskaičiuotiatstumo matrica tarp viršūnių a mi skaičius. Šiuo atveju tai bus dydžio matrica, kurioje yra atstumas nuo viršūnės iki viršūnės:

Kiekvienai matricos eilutei randame didžiausią elementą ir jį užrašome A va nuo linijos. Didžiausias iš šių skaičių lygus grafiko skersmeniui, mažiausias p A dius grafikas. Grafo centrą sudaro centrinės viršūnės ir.

Grafo centrinės viršūnės ir centro sąvokos atsirado dėl optinių problemų. Ir nedidelis viešųjų paslaugų teikimo punktų, tokių kaip ligoninės, gaisrinės, viešosios tvarkos punktai ir kt., išdėstymas, kai svarbu kuo labiau sumažinti Ir didesnis atstumas nuo bet kurio tinklo taško iki artimiausio aptarnavimo taško ir niya.

1. Pasiekiamumo ir priešpriešinio pasiekiamumo matricos

Pasiekiamumo matricaapibrėžiamas taip:

Grafo viršūnių aibė, pasiekiama iš nurodytos viršūnės, susideda iš tokių elementų, kurių matricos elementas yra lygus 1. Ši aibė gali būti pavaizduota kaip

Kontra-pasiekiamumo matrica (atvirkštinis pasiekiamumas) Aš apibrėžiau yra taip:

Panašiai kaip pasiekiamo rinkinio konstrukcijoje, galima formuoti daugybinį O gestas naudojant šią išraišką:

Iš apibrėžimų matyti, kad matricos stulpelis sutampa su matricos eilute T rits, t.y., kur yra matrica, perkelta į matricą.

2 pavyzdys. Raskite grafiko pasiekiamumo ir priešpriešinio pasiekiamumo matricas ir kt. Ir parodyta pav. 5.

Ryžiai. 5.

Apibrėžkime grafiko viršūnių pasiekiamumo rinkinius:

Todėl pasiekiamumo ir priešingo pasiekiamumo matricos yra tokios formos:

Kadangi yra aibė tokių viršūnių, kurių kiekviena priklauso bent vienam keliui, einančiam nuo iki, tai šios aibės viršūnės vadinamos ir yra esminiai arba neatskiriami galinių viršūnių atžvilgiu ir. Visos kitos viršūnės vadinamosnereikšmingas arba perteklinis , nes jų pašalinimas neturi įtakos takams nuo iki.

Taip pat galite apibrėžti matricas ribotas pasiekimai ir priešprieša Ir tiltai, jei reikalaujame, kad takų ilgiai neviršytų tam tikro skaičiaus. Tada bus viršutinė leistinų takų ilgio riba.

Grafas vadinamas tranzityviniu , jei nuo lankų ir pėdsakų egzistavimo adresu lanko nėra.Tranzityvus uždarymasgrafas yra grafikas, kuriame yra mažiausias galimas lankų rinkinys, reikalingas, kad grafikas būtų tranzityvus. Akivaizdu, kad grafo pasiekiamumo matrica sutampa su grafo gretimų matrica, jei į matricą įdėsite matricą pagrindinėje įstrižainėje.

Yra gana daug problemų, kuriose naudojama pasiekiamumo sąvoka. Štai vienas iš jų. Grafas gali būti tam tikros organizacijos modelis, kuriame žmonės vaizduojami viršūnėmis, o lankai interpretuoja komunikacijos kanalus. Svarstant tokį modelį, galima kelti klausimą, ar informacija iš vieno asmens x i gali būti perduota kitam asmeniui x j, tai yra, ar yra kelias, einantis iš viršūnės x i į viršūnę x j. Jei toks kelias egzistuoja, tai sakome, kad viršūnė x j pasiekiama iš viršūnės x i. Galima domėtis viršūnės x j pasiekiamumu iš viršūnės x i tik tuose keliuose, kurių ilgiai neviršija duotosios reikšmės arba kurių ilgis yra mažesnis už didžiausią viršūnių skaičių grafe ir pan.

Pasiekiamumas grafike apibūdinamas pasiekiamumo matrica R=, i, j=1, 2, ... n, kur n yra grafiko viršūnių skaičius, o kiekvienas elementas apibrėžiamas taip:

r ij =1, jei viršūnė x j pasiekiama iš x i,

r ij = 0, kitaip.

Daug viršūnių Grafo G R(x i), pasiekiamas iš tam tikros viršūnės x i, susideda iš tokių elementų x j, kurių (i, j) elementas pasiekiamumo matrica yra lygus 1. Akivaizdu, kad visi matricos R įstrižainės elementai yra lygūs 1, nes kiekviena viršūnė iš savęs pasiekiama 0 ilgiu. tiesioginis ekranas 1 eilė Г +1 (x i) yra viršūnių x j, kurios pasiekiamos iš x i naudojant 1 ilgio kelius, rinkinys, tada aibė Г + (Г +1 (x i)) = Г +2 (x i) susideda iš viršūnių, kurias galima pasiekti iš x i naudojant 2 ilgio kelius. Panašiai Г +p (x i) yra viršūnių, kurias galima pasiekti iš x i, aibė p ilgio takais.

Kadangi bet kuri grafiko viršūnė, kurią galima pasiekti iš x i, turi būti pasiekiama naudojant 0 arba 1 arba 2, ... arba p ilgio kelią (ar kelius), tada viršūnių rinkinys, pasiekiamas viršūnei x i, gali būti pavaizduotas formoje

Kaip matome, pasiekiamų viršūnių aibė R(x i) yra tiesi linija pereinamasis uždarymas viršūnės x i, t.y. R (x i) = T + (x i) . Todėl, norėdami sudaryti pasiekiamumo matricą, randame pasiekiamas aibes R (x i) visoms viršūnėms. Darant prielaidą, kad r ij =1, jei o kitaip r ij =0.

Ryžiai. 4.1.

Grafikui, parodytam pav.

Pasiekiamumo matrica 4.1,a, pasiekiamumo rinkiniai randami taip: atrodo kaip parodyta pav. 4.1,c.

Priešpriešinio pasiekiamumo matrica Pasiekiamumo matrica galima sukonstruoti naudojant gretimumo matricą (4.1 pav., b), sudarant aibes T + (x i) kiekvienai viršūnei x i.

Q = [ q ij ], i, j = 1, 2, ... n

, kur n yra grafo viršūnių skaičius, apibrėžiamas taip:

q ij =1, jei iš viršūnės x j galima pasiekti viršūnę x i,

q ij = 0, kitaip.

Pasiekiamumo grafikas Vienas iš pirmųjų klausimų, kylančių tiriant grafikus, yra kelių egzistavimo klausimas tarp duotųjų arba visų viršūnių porų. Atsakymas į šį klausimą yra aukščiau pateiktas pasiekiamumo ryšys grafo G=(V,E) viršūnėse: viršūnė w pasiekiama iš viršūnės v, jei v = w arba G turi kelią iš v į w. Kitaip tariant, pasiekiamumo ryšys yra refleksinis ir tranzityvus santykio E uždarymas. Nenukreiptiems grafams šis ryšys taip pat yra simetriškas, todėl yra viršūnių aibės V lygiavertiškumo santykis. Nenukreiptame grafe lygiavertiškumo klasės su pasiekiamumo santykio atžvilgiu vadinami sujungtais komponentais. Nukreiptų grafikų atveju pasiekiamumas neturi būti simetriškas. Abipusis pasiekiamumas yra simetriškas.

Apibrėžimas 9.8. Teigiama, kad nukreipto grafo G=(V,E) viršūnės v ir w yra abipusiai pasiekiamos, jei G turi kelią nuo v iki w ir kelią nuo w iki v. Akivaizdu, kad abipusio pasiekiamumo santykis yra refleksyvus, simetriškas ir tranzityvus, taigi ir lygiavertiškumas grafo viršūnių aibėje. Ekvivalentiškumo klasės abipusio pasiekiamumo atžvilgiu vadinamos stipriai susijusiais komponentais arba

dvigubai sujungti komponentai

grafiką. Pirmiausia panagrinėkime pasiekiamumo santykio konstravimo klausimą. Kiekvienam grafikui apibrėžiame jo pasiekiamumo grafiką (kartais dar vadinamą tranzityviniu uždarymo grafiku), kurio kraštai atitinka pradinio grafiko kelius.

Apibrėžimas 9.9. Tegu G=(V,E) yra nukreiptas grafikas. Pasiekiamumo grafikas G * =(V,E *), skirtas G, turi tą patį viršūnių rinkinį V, o kitą briaunų rinkinį E * =( (u, v) | grafe G viršūnė v pasiekiama iš viršūnės u) .

9.3 pavyzdys. Apsvarstykite grafiką G iš 9.2 pavyzdžio.

Ryžiai. 9.2.

G grafikas Tada galime patikrinti, ar G pasiekiamumo grafikas G* atrodo taip (naujos kiekvienos viršūnės 1-5 kilpos briaunos nerodomos):

Kaip iš grafiko G galima sudaryti grafiką G *? Vienas iš būdų – kiekvienai grafo G viršūnei nustatyti iš jos pasiekiamų viršūnių aibę, nuosekliai pridedant prie jos viršūnes, pasiekiamas iš jos 0, 1, 2 ir tt ilgio takais.

Apsvarstysime kitą metodą, pagrįstą grafiko G gretimų matricos A G ir Būlio operacijų naudojimu. Tegu viršūnių aibė V=(v 1 , … , v n ). Tada matrica A G yra n × n Būlio matrica.

Toliau, norėdami išlaikyti panašumą su įprastomis matricų operacijomis, Būlio operacijoms naudosime „aritmetinį“ žymėjimą: disjunkcijai žymėsime +, o konjunkcijai – ·.

Pažymėkime E n n × n dydžio tapatybės matricą. Padėkime . Tegul Mūsų G * konstravimo procedūra yra pagrįsta šiuo teiginiu.

Lemma 9.2. Tegul . Tada

Įrodymas Padarykime tai indukcija ant k.

Pagrindas. Jei k=0 ir k=1, teiginys yra teisingas pagal apibrėžimą ir .

Indukcinis žingsnis. Tegul lema teisinga k. Parodykime, kad jis galioja k+1. Pagal apibrėžimą mes turime:

Tarkime, kad grafe G yra kelias nuo v i iki v j, kurio ilgis yra k+1. Panagrinėkime trumpiausią iš šių kelių. Jei jo ilgis k, tai pagal indukcijos hipotezę a_(ij)^((k))=1. Be to, a jj (1) =1. Todėl a ij (k) a jj (1) =1 ir a ij (k+1) =1. Jei trumpiausio kelio nuo v i iki v j ilgis yra k+1, tai v r bus priešpaskutinė jo viršūnė. Tada nuo v i iki v r yra k ilgio kelias ir pagal indukcijos hipotezę a ir (k) =1. Kadangi (v r ,v j) E, tai a_(rj)^((1))=1. Todėl a ir (k) a rj (1) =1 ir a ij (k+1) =1.

Ir atvirkščiai, jei a ij (k+1) =1, tada bent vieno r suma a ir (k) a rj (1) yra lygi 1. Jei tai r=j, tai a ij (k) = 1 ir pagal indukcinę hipotezę G turi k ilgio kelią nuo v i iki v j. Jei r j, tai a ir (k) =1 ir a rj (1) =1. Tai reiškia, kad G turi k ilgio kelią nuo v i iki v r ir briauną (v r ,v j) E. Jas sujungę gauname k+1 ilgio kelią nuo v i iki v j.

Iš 9.1 ir 9.2 lemmų gauname tiesiogiai

1 išvada. Tegul G=(V,E) yra nukreiptas grafikas su n viršūnių, o G * – jo pasiekiamumo grafikas. Tada A_(G*) = . Įrodymas. Iš 5.1 lemos išplaukia, kad jei G turi kelią nuo u iki v u, tai jame taip pat yra paprastas kelias nuo u iki v, kurio ilgis n-1. Ir pagal 5.2 lemą visi tokie keliai yra pavaizduoti matricoje.

Taigi, G pasiekiamumo grafiko gretimų matricos A G* sudarymo procedūra sumažinama iki matricos pakėlimo iki n-1 laipsnio. Norėdami supaprastinti šią procedūrą, pateiksime keletą pastabų.

čia k yra mažiausias skaičius, kad 2 k n.

Jei r randamas toks, kad a ir = 1 ir a rj = 1, tada visa suma a ij (2) =1. Todėl į likusias sąlygas galima nepaisyti.

Apibrėžimas 9.9. Panagrinėkime, kaip pavyzdį, pasiekiamumo grafiko A G* matricos apskaičiavimą diagramai G pateiktam. 9.2 pav. Šiuo atveju

Kadangi G turi 6 viršūnes, tada . Apskaičiuokime šią matricą:

ir (paskutinę lygybę nesunku patikrinti). Taigi,

Kaip matome, ši matrica iš tikrųjų apibrėžia pateiktą grafiką 9.3 pav.

Abipusis pasiekiamumas, stipriai susiję komponentai ir grafikų bazės

Analogiškai su pasiekiamumo grafiku apibrėžiame stiprią pasiekiamumo grafiką.

Apibrėžimas 9.10. Tegu G=(V,E) yra nukreiptas grafikas. Stipraus pasiekiamumo grafikas G * * =(V,E * *), skirtas G, turi tą patį viršūnių rinkinį V ir kitą briaunų rinkinį E * * =( (u, v) | grafe G viršūnės v ir u yra abipusiai pasiekiami).

Naudojant pasiekiamumo grafiko matricą, nesunku sudaryti stipraus pasiekiamumo grafiko matricą. Iš tiesų, iš pasiekiamumo ir stipraus pasiekiamumo apibrėžimų iš karto matyti, kad visoms poroms (i,j), 1 i,j n elemento reikšmė yra 1 tada ir tik tada, kai abu elementai A G* (i, j) ir A G * (j, i) yra lygūs 1, t.y.

Remiantis matrica, stipriai susietas grafiko G komponentes galime nustatyti taip.

Sudėkime į komponentą K 1 viršūnę v 1 ir visas viršūnes v j taip, kad A_(G_*^*)(1,j) = 1.

Tegul komponentai K 1, …, K i ir v k jau yra sukonstruoti - tai viršūnė su mažiausiu skaičiumi, kuri dar nebuvo įtraukta į komponentus. Tada į komponentą K_(i+1) dedame viršūnę v k ir visas tokias viršūnes v j ,

kad A_(G_*^*)(k,j) = 1.

Kartojame (2) veiksmą, kol visos viršūnės bus paskirstytos tarp komponentų.

Mūsų pavyzdyje grafui G ant 2 pav iš matricos gauname tokią stipraus pasiekiamumo grafiko matricą

Naudodami aukščiau aprašytą procedūrą, nustatome, kad grafo G viršūnės suskirstytos į 4 stipraus ryšio komponentus: K 1 = (v 1, v 2, v 3), \ K 2 =( v 4), \ K 3 =( v 5), \ K 4 =( v 6 ). Tvirtai susijusių komponentų rinkinyje taip pat apibrėžiame pasiekiamumo ryšį.

Apibrėžimas 9.11. Tegu K ir K" yra stipriai sujungti grafiko G komponentai. Komponentas K pasiekiamas iš komponentai K^\pirminiai, jei K= K" arba yra dvi viršūnės u K ir v K", kad u būtų pasiekiamas iš v. K griežtai pasiekiamas nuo K^\pirminis, jei K K" ir K pasiekiamas iš K". Komponentas K vadinamas minimumas, jei jis nėra griežtai pasiekiamas iš kurio nors komponento.

Kadangi visos vieno komponento viršūnės yra tarpusavyje pasiekiamos, nesunku suprasti, kad pasiekiamumo ir griežto pasiekiamumo santykiai komponentuose nepriklauso nuo viršūnių u K ir v K pasirinkimo.

Iš apibrėžimo nesunkiai išvedama tokia griežto pasiekiamumo savybė.

Lemma 9.3. Griežtas pasiekiamumo santykis – tai dalinės tvarkos santykis, t.y. jis yra antirefleksinis, antisimetriškas ir tranzityvus.

Šį ryšį galima pavaizduoti kaip nukreiptą grafą, kurio viršūnės yra komponentai, o kraštas (K, K) reiškia, kad K yra griežtai pasiekiamas iš K". Įjungta ryžių. 9.4šis komponentų grafikas parodytas aukščiau aptartam grafikui G.

Ryžiai. 9.4.

Šiuo atveju yra vienas minimalus komponentas K 2 .

Daugelyje programų nukreiptas grafikas vaizduoja tam tikrų išteklių paskirstymo tinklą: produktą, prekes, informaciją ir kt. Tokiais atvejais natūraliai iškyla užduotis surasti minimalų skaičių tokių taškų (viršūnių), iš kurių šis resursas gali būti pristatytas į bet kurį tinklo tašką.

Apibrėžimas 9.12. Tegu G=(V,E) yra nukreiptas grafikas. Vadinamas viršūnių W V poaibis generuojantys, jei iš W viršūnių galima pasiekti bet kurią grafo viršūnę. Viršūnių W V poaibis vadinamas grafo pagrindu, jei jis generuoja, bet joks tinkamas jo poaibis negeneruoja.

Ši teorema leidžia efektyviai rasti visas grafo bazes.

9.1 teorema. Tegu G=(V,E) yra nukreiptas grafikas. Viršūnių W V poaibis yra G pagrindas tada ir tik tada, kai jame yra viena viršūnė iš kiekvieno minimaliai stipriai sujungto G komponento ir nėra jokių kitų viršūnių.

Įrodymas Pirmiausia atkreipkime dėmesį, kad kiekviena grafo viršūnė pasiekiama iš viršūnės, priklausančios kokiam nors minimaliam komponentui. Todėl viršūnių rinkinys W, kuriame yra po vieną viršūnę iš kiekvieno minimalaus komponento, generuojasi, o kai iš jos pašalinama bet kuri viršūnė, ji nustoja tokia būti, nes viršūnės iš atitinkamo minimalaus komponento tampa nepasiekiamos. Todėl W yra pagrindas.

Ir atvirkščiai, jei W yra pagrindas, tada jis turi apimti bent vieną viršūnę iš kiekvieno minimalaus komponento, kitaip tokio minimalaus komponento viršūnės bus nepasiekiamos. W negali būti jokių kitų viršūnių, nes kiekviena iš jų pasiekiama iš jau įtrauktų viršūnių.

Iš šios teoremos seka tokia procedūra, kaip sudaryti vieną arba surašyti visas grafo G bazes.

Raskite visus stipriai susijusius G komponentus.

Nustatykite jų tvarką ir pasirinkite minimalius komponentus, susijusius su šia tvarka.

Sukurkite vieną arba visas grafiko bazes, pasirinkdami vieną viršūnę iš kiekvieno minimalaus komponento.

9.5 pavyzdys. Apibrėžkime visas pavaizduoto nukreipto grafo G bazes 9.5 pav.

Ryžiai. 9.5. Apsvarstykite grafiką G iš 9.2 pavyzdžio.

Pirmajame etape randame stipriai sujungtus G komponentus:

Antrame etape sudarome griežtą šių komponentų pasiekiamumo grafiką.

Ryžiai. 9.6. G komponentų pasiekiamumo ryšių grafikas

Apibrėžiame minimalius komponentus: K 2 = ( b ), K 4 = ( d, e, f, g) ir K 7 = ( r).

Galiausiai išvardijame visas keturias G bazes: B 1 = ( b, d, r), B 2 = ( b, e, r), B 3 = ( b, f, r) ir B 1 = ( b, g, r) .

Užduotys

9.1 problema.Įrodykite, kad savavališko nukreipto grafo visų viršūnių laipsnių suma yra lygi.

Ši problema turi populiarią interpretaciją: įrodykite tai bendras skaičius Vakarėlyje dalyvaujančių žmonių rankos paspaudimų skaičius visada yra lygus.

9.2 problema. Išvardykite visus neizomorfinius neorientuotus grafikus, turinčius daugiausia keturias viršūnes.

9.3 problema.Įrodykite, kad nenukreiptas sujungtas grafikas lieka prijungtas pašalinus kokią nors briauną ↔ ši briauna priklauso kokiam nors ciklui.

9.4 problema.Įrodykite, kad neorientuotas sujungtas grafas su n viršūnių

turi bent n-1 briaunų,

jei jame yra daugiau nei n-1 briaunos, tada jis turi bent vieną ciklą.

9.5 uždavinys.Įrodykite, kad bet kurioje 6 žmonių grupėje yra trys poros pažįstamų arba trys poros nepažįstamų žmonių.

9.6 problema.Įrodykite, kad nenukreiptas grafas G=(V,E) sujungtas ↔ kiekvienai V= V 1 V 2 daliai su netuščiomis V 1 ir V 2 yra briauna, jungianti V 1 su V 2 .

9.7 problema.Įrodykite, kad jei nenukreiptasis grafikas turi lygiai dvi nelyginio laipsnio viršūnes, tai jos yra sujungtos keliu.

9.8 uždavinys. Tegu G=(V,E) yra nenukreiptas grafikas su |E|< |V|-1. Докажите, что тогда G несвязный граф.

9.9 uždavinys.Įrodykite, kad sujungtame nekryptiniame grafe bet kurie du paprasti keliai maksimalus ilgis turi bendrą viršūnę.

9.10 uždavinys. Tegul nenukreiptas grafikas be kilpų G=(V,E) turi k sujungtų komponentų. Įrodyk tai tada

9.11 uždavinys. Nustatykite, kam skirtas pasiekiamumo grafikas

grafas su n viršūnių ir tuščia briaunų rinkiniu;

grafas su n viršūnių: V= (v 1 ,… , v n ), kurio briaunos sudaro ciklą:

9.12 uždavinys. Apskaičiuokite grafiko pasiekiamumo grafiko matricą

ir sudaryti atitinkamą pasiekiamumo grafiką. Raskite visas grafo G bazes.

9.13 uždavinys. Sukurti už duotą ryžių. 9.7 nukreiptas grafikas G 1 =(V,E) jo gretimų matrica A G1, dažnumo matrica B G1 ir gretimų sąrašai. Apskaičiuokite pasiekiamumo matricą A G1* ir sukurkite atitinkamą pasiekiamumo grafiką G1*.

Ryžiai. 9.7.

Nenukreipti ir nukreipti medžiai

Medžiai yra viena iš įdomiausių grafikų klasių, naudojamų įvairiems hierarchinių struktūrų tipams pavaizduoti.

Apibrėžimas 10.1. Nenukreiptas grafikas vadinamas medžiu, jei jis yra sujungtas ir neturi ciklų.

Apibrėžimas 10.2. Nukreiptas grafikas G=(V,E) vadinamas (nukreiptu) medžiu, jei

Įjungta ryžių. 10.1 rodomi nenukreipto medžio G 1 ir nukreipto medžio G 2 pavyzdžiai. Atkreipkite dėmesį, kad medis G 2 gaunamas iš G 1, pasirinkus viršūnę c kaip šaknį ir nukreipiant visas briaunas kryptimi nuo šaknies.

Ryžiai. 10.1. Nenukreipti ir nukreipti medžiai

Tai nėra atsitiktinumas. Įrodykite šį teiginį apie ryšį tarp nekrypstamų ir nukreiptų medžių.

Lemma 10.1. Jeigu kokiame nors nenukreiptame medyje G=(V,E) šaknimis pasirenkame savavališką viršūnę v V ir visas briaunas orientuojame „nuo šaknies“ kryptimi, t.y. padaryti v visų į jį patenkančių briaunų pradžią, viršūnes, esančias greta v, visų dar neorientuotų kraštinių, patenkančių į jį, pradžia ir pan., tada gautas nukreiptas grafikas G" bus nukreiptas medis.

Nenukreipti ir nukreipti medžiai turi daug lygiaverčių savybių.

10.1 teorema. Tegu G=(V,E) yra nenukreiptas grafikas. Tada šios sąlygos yra lygiavertės.

G yra medis.

Bet kurioms dviem G viršūnėms yra unikalus kelias, jungiantis jas.

G yra sujungtas, bet pašalinus bet kurią briauną nuo E, jis nustoja būti sujungtas.

G yra prijungtas ir |E| = |V| -1.

G yra aciklinis ir |E| = |V| -1.

G yra aciklinis, bet pridėjus bet kurią briauną prie E gaunamas ciklas.

Įrodymas(1) (2): Jei kai kurios dvi G viršūnės būtų sujungtos dviem keliais, tada akivaizdu, kad G turėtų ciklą. Bet tai prieštarauja medžio apibrėžimui (1).

(2) (3): Jei G yra sujungtas, bet pašalinus kokią nors briauną (u,v), E nepraranda ryšio, tai tarp u ir v yra kelias, kuriame nėra šios briaunos. Bet tada G yra bent du keliai, jungiantys u ir v, o tai prieštarauja sąlygai (2).

(3) (4): pateikiama skaitytojui (žr. 9.4 uždavinį).

(4) (5): Jei G yra ciklas ir yra sujungtas, tai pašalinant bet kurią ciklo briauną, jungtis neturėtų būti nutraukta, bet briaunos išliks |E|= V -2, o pagal 9.4 uždavinį a) sujungtame grafike turi būti bent V -1 briaunos. Gautas prieštaravimas rodo, kad G nėra ciklų ir (5) sąlyga yra įvykdyta.

(5) (6): Tarkime, kad pridėjus briauną (u,v) prie E neatsirado ciklas. Tada G viršūnės u ir v yra skirtinguose sujungtuose komponentuose. Kadangi |E|= V -1, tai viename iš šių komponentų tebūnie (V 1 ,E 1), briaunų skaičius ir viršūnių skaičius sutampa: |E 1 |=|V 1 |. Bet tada jis turi ciklą (žr. 9.4 (b) uždavinį), kuris prieštarauja G acikliškumui.

(6) (1): Jei G nebūtų prijungtas, tada būtų dvi viršūnės u ir v iš skirtingų sujungtų komponentų. Tada prie E pridėjus briauną (u,v), neatsirastų ciklas, o tai prieštarauja (6). Todėl G yra sujungtas ir yra medis.

Nukreiptiems medžiams dažnai patogu naudoti šį indukcinį apibrėžimą.

Apibrėžimas 10.3. Apibrėžkime indukcija nukreiptų grafikų, vadinamų medžiais, klasę. Tuo pačiu kiekvienai iš jų apibrėžiame pasirinktą viršūnę – šaknį.

Ryžiai. 10.2 iliustruoja šį apibrėžimą.

Ryžiai. 10.2. Indukcinis orientuotų medžių nustatymas

10.2 teorema. Nukreiptų medžių 10.2 ir 10.3 apibrėžimai yra lygiaverčiai.

Įrodymas Tegul grafikas G=(V,E) tenkina 10.2 apibrėžimo sąlygas. Viršūnių skaičiaus |V| indukcija parodykime, kad .

Jei |V|=1, tai vienintelė viršūnė v V pagal savybę (1) yra medžio šaknis, t.y. šiame grafike nėra briaunų: E = . Tada .

Tarkime, kad kiekvienas grafas su n viršūnių, atitinkantis 10.2 apibrėžimą, yra įtrauktas į . Tegul grafikas G=(V,E) su (n+1) viršūne tenkina 10.2 apibrėžimo sąlygas. Pagal sąlygą (1) jis turi viršūnės šaknį r 0 . Tegul iš r 0 atsiranda k briaunų ir jos veda į viršūnes r 1 , ... , r k (k 1). Pažymime G i ,(i=1, …, k) grafą, apimantį viršūnes V i =( v V|v \textit( pasiekiamas iš )r i ) ir jas jungiančias briaunas E i E kad G i tenkina 10.2 apibrėžimo sąlygas. Išties r i neapima briaunų, t.y. ši viršūnė yra G i šaknis. Kiekvienoje likusioje V i viršūnėje yra viena briauna, kaip G. Jei v V i , tai jis pasiekiamas iš šaknies r i pagal grafiko G i apibrėžimą. Nuo |V i | n, tada pagal indukcinę hipotezę . Tada grafikas G gaunamas pagal 10.3 apibrėžimo indukcinę taisyklę (2) iš medžių G 1, ..., G k ir todėl priklauso klasei.

⇐ Jei koks nors grafikas G=(V,E) yra įtrauktas į klasę , tai 10.2 apibrėžimo sąlygų (1)-(3) įvykdymą jam galima nesunkiai nustatyti indukcija naudojant 10.2 apibrėžimą. Tai paliekame skaitytojui kaip pratimą.

Su orientuotais medžiais siejama daugybė terminų, gaunamų iš dviejų šaltinių: botanikos ir šeimos santykių srities.

Šaknis yra vienintelė viršūnė, kuri neturi kraštų, lapai yra vienintelės viršūnės, kurios neturi kraštų. Kelias nuo šaknies iki lapo vadinamas medžio šaka. Medžio aukštis yra didžiausias jo šakų ilgis. Viršūnės gylis yra kelio ilgis nuo šaknies iki tos viršūnės. Viršūnei v V medžio T=(V,E) pografas, apimantis visas iš v pasiekiamas viršūnes ir jas jungiančias briaunas iš E, sudaro medžio T pomedį T v su šaknimi v (žr. 10.3 uždavinį). Viršūnės aukštis v yra medžio aukštis T v. Grafikas, sudarytas iš kelių nesusijusių medžių, vadinamas mišku.

Jei briauna veda iš viršūnės v į viršūnę w, vadinasi v tėvas w ir w - sūnus v (pastaruoju metu anglų kalbos literatūroje vartojama aseksuali terminų pora: tėvas – vaikas). Iš medžio apibrėžimo iš karto matyti, kad kiekviena viršūnė, be šaknies, turi vieną tėvą. Jei kelias veda iš viršūnės v į viršūnę w, tada v vadinamas w protėviu, o w – v palikuonimi. Vadinamos viršūnės, turinčios bendrą tėvą broliai arba seserys.

Išskirkime dar vieną grafikų klasę, kuri apibendrina orientuotus medžius – orientuotus aciklinius. Dviejų tipų tokie pažymėti grafikai vėliau bus naudojami Būlio funkcijoms pavaizduoti. Šie grafikai gali turėti kelias šaknis – viršūnes, kuriose nėra briaunų, o kiekvienoje viršūnėje gali būti kelios briaunos, o ne tik viena, kaip medžiai.

kompiuteris technologijas, ypač programa ... 2009 metų Pradinė mokykla yra eksperimentinė svetainė Autorius federalinio įvadas valstybė ...

M MEDIA MONITORINGAS Profesinio mokymo modernizavimas 2011 kovo - rugpjūčio mėn

Santrauka

Jungtinė valstybė egzaminai" Autorius pasirinkimas": informacinis kompiuteristechnologijas, biologija ir literatūra. Beje, šiame metų Vieningas valstybinis egzaminas... klausimas„Apie įgyvendinimo rezultatus programas nacionalinės raidos mokslinių tyrimų universitetai V 2009 -2010 metai“. ...

STRATEGINĖS PLĖTROS PROGRAMA Tverės 2011 m

Programa

IN 2009 metų. Struktūriniai pokyčiai, pastebėti 2010 m metųAutorius link 2009 , ... Profesionaliai – orientuotas užsienio kalba“, „Šiuolaikinis ugdymas technologijos“. Kiekviename programa diegiamas išplėstinio mokymo modulis “ valstybė ...