Grafo viršūnių laipsnių sekos

Grafo viršūnių laipsnių sekos

Paragrafe 2.2 apibrėžėme viršūnės v laipsnį r(v) ir grafo viršūnių laipsnių seką r r(v₁), r(v₂), … , r(v_n). Čia plačiau panagrinėsime kokias grafo savybes nusako jo viršūnių laipsnių seka, ką bendro turi grafai, turintįs vienodas viršūnių laipsnių sekas, kaip sukonstruoti grafą pagal duotą viršūnių laipsnių seką, ir turintį vienokias ar kitokias savybes.

Grafinės sekos

Įveskime keletą apibrėžimų.

Sveikų neneigiamų skaičių seką d₁,d₂,…,d_n vadinsime n-seka ir žymėsime d. Jei egzistuoja grafas su viršūnių laipsnių seka r sutampančia su n-seka d, tai šią n-seką vadinsime grafine n-seka, o ją atitinkantį grafą - sekos d realizacija. n-seką vadinsime taisyklinga n-seka, jei tenkinamos dvi sąlygos:

,

lyginis skaičius.

Grafinė n-seka yra taisyklinga.

Kartais d-seką patogu užrašyti taip: , kur - tarpusavyje skirtingi skaičiai, o laipsnio rodiklis nurodo, kiek kartų skaičius kartojasi sekoje d. Pavyzdžiui,

Bendru atveju grafinė seka turi daug realizacijų ir nustatyti jų skaičių yra sunku. Pavyzdžiui, grafinė n-seka turi penkias realizacijas (žr. pav.). Čia

C_n – n-viršūninis paprastasis ciklas,

K_n – n-viršūninis pilnas grafas,

P_n – n-viršūninė paprastoji grandis.

Galime nustatyti ryšį tarp kelių tos pačios grafinės sekos realizacijų. Įveskime perjungimo sąvoką. Tegul duotas grafas G (V,U), a,b,c,dIV (a,b),(c,d)IU Viršūnės a ir c , bei b ir d tarpusavyje briaunomis nesujungtos. Tada sakome, kad grafe G galimas perjungimas s (ab,cd), kurį atlikus gaunamas grafas sG G-(a,b)-(c,d)+(a,c)+(b,d). Pavyzdžiui, 2.2 pav. parodyti grafai G ir sG, kur s

Akivaizdu, kad perjungimas nekeičia grafo viršūnių laipsnių sekos. Perjungimo prasmę nusako žemiau pateikta teorema.

pav Penkios grafinės n-sekos realizacijos

pav Grafas G ir po perjungimo s ((1,3),(4,2)) gautas grafas sG.

Teorema. Bet kuri grafinės sekos realizacija gaunama iš bet kurios kitos tos grafinės sekos realizacijos atlikus atitinkamą perjungimų seką.

Šios teoremos įrodymas remiasi tokia lema.

Lema. Tarkime G – grafas, kurio viršūnės sunumeruotos skaičiais 1, 2, , n taip, kad viršūnių laipsniai sudaro nedidėjančią seką , tai yra V=, Tada bet kuriai grafo viršūnei i egzistuoja tokia perjungimų s₁, s₂,, s_t seka, kad grafo H= s₁, s₂,, s_t G viršūnės i gretimų viršūnių aibė N_H(i) sutampa su sekos didžiausio laipsnio viršūnių aibe, t.y.

Kartais, nors ir retai, grafą vienareikšmiškai nusako jo viršūnių laipsnių seka. Jeigu visos grafinės sekos realizacijos yra izomorfiniai grafai, tai ši grafinė seka vadinama unigrafine seka, o jos realizacija - unigrafu. Pavyzdžiui, paprastasis ciklas C₅ yra unigrafas.

Grafinės sekos kriterijai

Jau minėjome, kad grafinę seką visada galima laikyti taisyklinga n-seka. Tačiau atvirkštinis teiginys nėra teisngas – n-sekos taisyklingumas yra būtina, bet nepakankama sąlyga, kad n-seka būtų grafine. Pavyzdžiui, seka nėra grafinė seka.

Havelo – Chakimi kriterijus. Tegul d – taisyklinga n-seka, n>1. Pažymėkime cⁱ , (n-1)-seką, gautą iš n-sekos d išbraukus i-ąjį narį:

Iš sekos cⁱ gaukime seką sumažindami vienetu pirmuosius narius, t.y.

Tada vadinsime išvestine seka.

Pavyzdžiui, jeigu  d = (3, 3, 1, 1), tai , .

Teorema. (Havelas V.1955 Chakimi S. 1962). Tegul d – taisyklinga n-seka (n>1). Jeigu kuriam tai indeksui i, , išvestinė seka yra grafinė seka, tai ir d seka yra grafinė seka. Jei seka d yra grafinė seka, tai ir kiekviena išvestinė seka () yra grafinė seka.

Erdeš – Gallai kriterijus. Šį grafinės sekos kriterijų nusako tokia teorema.

Teorema. (Erdeš P. Gallai T. 1960). Taisyklinga n-seka yra grafinė tada ir tik tada, kai kiekvienam teisinga nelygybė .

Įrodyta, kad jei ši nelygybė galioja kai , čia , tai ji galioja ir visoms likusioms k reikšmėms. Tai supaprastina Erdeš – Gallai kriterijaus taikymą n-sekos testavimui.

Grafinės sekos realizacijos algoritmas

Aprašytasis Havelo -Chakimi kriterijus leidžia atpažinti, ar duotoji taisyklinga n-seka yra grafinė ir rasti vieną iš sekos realizacijų. Pavadinkime šį algoritmą l-procedūra.

Duota: d – taisyklinga n-seka, t.y.

,

lyginis skaičius.

Rasti: d sekos grafinę realizaciją arba įsitikinti, kad ši seka tokios realizacijos neturi.

Tegul: V= – būsimo grafo viršūnių aibė, kur kiekvienai aibės viršūnei v ( ) skirta atitinkama d(v) reikšmė,

S(v) – viršūnių V poaibis, sudarytas iš tų viršūnių , kurioms reikšmės yra maksimalios. Aibės S(v) elementų skaičius yra lygus d(v) ir, bendru atveju ši aibė nusakoma nevienareikšmiškai.

Taigi l-procedūros eilinis žingsnis būtų toks:

fiksuoti bet kurią viršūnę v, kuriai d(v)>0 (viršūnė v vadinama vedančiąja viršūne};

sudaryti vieną iš galimų aibių S(v);

vedančiąją viršūnę v sujungti briaunomis su visomis aibės S(v) viršūnėmis;

pakeisti d reikšmes vedančiajai viršūnei v ir kiekvienai aibės S(v) viršūnei u, nustatant d(v)=0 ir d(u)=d(u)-1. Jei vykdant šį žingsnį kuri nors d reikšmė tampa neigiama, reiškia seka neturi grafinės realizacijos.

Pavyzdys Pritaikykime l-procedūrą tokiai n-sekai 2.3 pav. kiekvienas stulpelis vaizduoja vieną l-procedūros žingsnį, parenkantį vedančiąją viršūnę (pažymėta žvaigždute), jai pavaldžiųjų viršūnių aibę S(v) ir kiekvienos viršūnės d reikšmės kitimą (pažymėta skliausteliuose). Čia vedančiosios viršūnės - ir S(1) , S(2) , S(4)=.

pav Grafinė sekos realizacija taikant l-procedūrą

Maksimaliai jungi grafinės sekos realizacija

Maksimaliai jungi grafinės sekos realizacija, yra tas grafas iš visų galimų grafinių realizacijų, kuriame briauninio jungumo skaičius yra maksimalus.

Tegul d – taisyklinga grafinė n-seka. Kadangi bet kuriam grafui G galioja nelygybė (kur - minimalus grafo viršūnių laipsnis) , stengsimės rasti grafinę realizaciją, kurioje .

Pradžioje stengsimės sudaryti jungiąją grafinės sekos realizaciją.

Teorema. Taisyklinga grafinė seka gali būti realizuota jungiuoju grafu tada ir tik tada, kai d_n> 0 ir teisinga nelygybė Jeigu tenkinamos šios sąlygos l-procedūra, kiekviename žingsnyje vedančiąja viršūne parinkdama viršūnę su minimalia teigiama d reikšme, sukonstruos jungųjį grafą.

Pastaba. Kai d_n >1 teoremos nelygybė tenkinama automatiškai.

Teorema. n-seka d gali būti realizuota medžiu tada ir tik tada, kada ji neturi nulinių reikšmių ir galioja lygybė Modifikuota l-procedūra, pavadinkime ją lm-procedūra, kiekviename žingsnyje vedančiąja viršūne parinkdama viršūnę su minimalia teigiama d reikšme, sukonstruos grafą – medį.

Pavyzdžiui, seka tenkina teoremoje pateiktą lygybę įstačius d reikšmes gauname 3+3+2+1+1+1+1=12. Taigi, seka gali būti realizuota medžiu. Tai atliekančios lm-procedūros žingsniai ir sukonstruotas medis pavaizduoti pav. Čia minimalios teigiamos d reikšmės paieška vykdoma einant nuo sekos d pabaigos į jos pradžią.

pav. lm-procedūra konstruojanti medį iš sekos

Pateikta teorema leidžia atpažinti, ar duotosios taisyklingos n-sekos realizacija gali būti medis ir modifikuoti l-procedūrą šio medžio konstravimui. Šį algoritmą pavadinome lm-procedūra.

Tegul d – taisyklinga n-seka,

V= – būsimo grafo viršūnių aibė, kur kiekvienai aibės viršūnei v ( ) skirta atitinkama d(v) reikšmė,

ved_vIV – vedančiųjų viršūnių aibė |ved_v|= n-1, t.y. algoritmo vykdymo eigoje parenkama viršūnė, turinti einamuoju momentu mažiausią d reikšmę, ir jungiama su kita viršūne (pavaldžiąja), einamuoju momentu turinčia didžiausią reikšmę sekoje d; algoritmo eigoje d sekos reikšmės kinta: parinkus vedančiąją ir jai pavaldžiąją viršūnes jų abiejų d reikšmės sumažinamos vienetu; kadangi einamuoju momentu sekoje d gali būti kelios minimalios reikšmės, renkant vedančiąją viršūnę, ir kelios maksimalios reikšmės, renkant pavaldžiąją viršūnę, sekos grafinė realizacija - medis nėra nusakomas vienareikšmiškai;

pav_vIV – pavaldžiųjų viršūnių aibė |pav_v|= n-1, kiekvienai vedančiajai viršūnei iš aibės ved_v parinkta pavaldžioji viršūnė įrašoma į aibę pav_v.

seka – kintamasis, įgaunantis reikšmes TRUE, jei galioja teoremos sąlygos ir d_n> 0, arba FALSE priešingu atveju, kas reiškia, kad pagal duotąją seką negali būti sukonstruotas medis.

type mas= array [1..100] of integer;

procedure lm (n: integer;d: mas;var ved_v, pav_v:mas; var seka:BOOLEAN );

var i,j,sum,max,min,w:integer;

begin

sum:=

if d[n]<>0 then

begin

for i:=1 to n do

sum:=sum+d[i];

if sum=2*(n-1)

then

begin

seka:=TRUE;

for w:=1 to n-1 do

begin

min:=n; j:=

for i:=n downto 1 do

if(d[i]<min)and(d[i]<>0)

then begin min:=d[i]; j:=i end;

ved_v[w]:=j;

d[j]:=d[j]-1;

max:=0; j:=0;

for i:=1 to n do

if d[i]>max

then begin max:= d[i]; j:=i end;

pav_v[w]:=j;

d[j]:=d[j]-1;

end;

end

else seka:=FALSE

end

else seka:=FALSE;

end;

Hamiltono grafo konstravimas pagal grafinę seką

Teorema. (Tshangfeizen V. 1978) Jei egzistuoja taisyklingos n-sekos realizacija d turinti Hamiltono grandinę prasidedančią d_i laipsnio viršūnėje, tai tokį grafą realizuos taip modifikuota l-procedūra (pavadinkime ją lh-procedūra): pirmame žingsnyje vedančiąja viršūne imama d_i laipsnio viršūnė, o kiekviename sekančiame žingsnyje viršūnė, turinti mažiausią teigiamą d reikšmę iš aibės S(v), kur v-vedančioji priešbuvusio žingsnio viršūnė, o S(v)-viršūnei v pavaldžiųjų viršūnių aibė.

Teorema. (Tshangfeizen V. 1978) Kad taisyklingos n-sekos d realizacija būtų grafas, turintis Hamiltono ciklą, turi būti tenkinamos tokios dvi sąlygos:

d_i> 1, ;

seka d gali būti realizuota Hamiltono grandine, prasidedančia d₁ laipsnio viršūnėje.

Paveiksle 2.5 pav. parodyta sekos realizacija Hamiltono grafu, lh procedūroje pirmąja vedančiąja viršūne parinkus pirmąją viršūnę. Gauta Hamiltono grandinė: 1, 4, 2, 5, 6, 3, kurią sudaro vedančiųjų viršūnių aibė ir paskutinei vedančiajai viršūnei pavaldi viršūnė S(6)=3. Kadangi ši viršūnė yra ir pirmajai vedančiajai viršūnei (pradinei grandies viršūnei) pavaldžių viršūnių aibėje S(1)=, gautoji realizacija turi ir Hamiltono ciklą : 1, 4, 2, 5, 6, 3, 1.

pav Sekos realizacija Hamiltono grafu taikant lh-procedūrą

Nuo anksčiau aprašytos l-procedūros lh-procedūra skiriasi tuo, kad:

nefiksuojamas vedančiųjų viršūnių skaičius – jų turi būti n, kad susidarytų Hamiltono grandinė. Tiesa, čia paskutinė viršūnė vedančiųjų viršūnių sąraše yra priešpaskutinės vedančiosios viršūnės pavaldžioji viršūnė, kuri jau nebeturi jai pavaldžių viršūnių;

nurodoma viršūnė v, nuo kurios pradedama ieškoti Hamiltono grandinės (ciklo). Pagal pirmąją šio skyrelio teoremą, norint sužinoti, ar grandinė iš viso yra, pradedama nuo pirmos viršūnės.

Paveiksluose 2.6 pav. ir 2.7 pav. parodyti dar du bandymai realizuoti grafines sekas Hamiltono grafais taikant lh-procedūrą.

pav. Sekos realizacija Hamiltono grafu taikant lh-procedūrą

pav Seka neturi Hamiltono realizacijos