Diplominio darbo, magistro laipsniui įgyti „Kai kurios briauninių grafų savybės” tikslas -apžvelgti grafų teorijos atsiradimo istoriją, panagrinėti grafų rūšis, savybes, veiksmus su grafais, pabandyti savarankiškai įrodyti kelias briauninių grafų savybes. Darbas susideda iš dviejų skyrių. Pirmajame skyriuje „Grafų tipai” apžvelgiamos grafų teorijos istorinės aplinkybės, išdėstyta reikalinga teorinė medžiaga, apžvelgiamos grafų rūšys bei veiksmai su grafais, pateikiama grafų, iliustruojančių nagrinėjamas sąvokas, pavyzdžių. Antrajame skyriuje „Kai kurios briauninių grafų savybės”, remiantis pirmojo skyriaus medžiaga, pateiktos savarankiškai įrodytos teoremos.
Atsisiųsti briaunines-grafos
Grafas – figūra, sudaryta iš taškų (vadinamų viršūnėmis) ir iš atkarpų, jungiančių kai kurias šių viršūnių. Jungiančios atkarpos gali būti tiesios arba kreivos, jos vadinamos grafo briaunomis.
Grafų teorijos atsiradimas XVIII amžiuje yra susijęs su matematiniais galvosūkiais, todėl gana ilgai į grafų mokslą buvo žiūrima kaip į „nerimtą” temą, kurios „taikomoji” vertė susijusi tik su lošimais ir pramogomis.
XX amžiaus pradžioje grafai patraukė topologų dėmesį, todėl pirmoje praeito amžiaus pusėje grafų teorija buvo laikoma sudėtingos šiuolaikinės matematikos šakos, kuria domisi tik siauras specialistų ratas – topologijos dalimi. Vėliau paaiškėjo, kad grafų teorija labai naudinga, sprendžiant daugelį svarbių praktikos klausimų, iš kurių čia verta paminėti vadinamuosius „transporto uždavinius” (racionaliausios krovinių pervežimo sistemos transporto tinkle planavimo uždaviniai), uždavinius susijusius su elektros tinklais, bei grafų teorijos taikymą tokiose srityse kaip ekonomika, psichologija ir biologija
Grafų teorijos pradininku laikomas Euleris (1707-1782), 1736m. išsprendęs žinomą tuomet uždavinį apie Karaliaučiaus tiltus. Karaliaučiuje buvo dvi salos, sujungtos septyniais tiltais su upės Prėgliaus krantais ir tarpusavyje taip, kaip parodyta 1 piešinyje.
Reikėjo sugalvoti, kaip būtų galima pereiti visas keturias sausumos dalis (pradedant bet kuria iš jų), pereinant per kiekvieną tiltą tik po vieną kartą ir grįžtant į tą pačią sausumos dalį. Atrodytų, lengva būtų surasti tokį kelią bandymų būdu, bet visos pastangos baigdavosi nesėkmingai. Euleris įrodė, kad tokio kelio nėra.
Tam, kad įrodytų tai, Euleris kiekvieną sausumos dalį pažymėjo tašku (viršūne), o kiekvieną tiltą – linija (briauna), jungiančią atitinkamus taškus. Taip atsirado „grafas”. 2 piešinys.
2 pieš. Grafas uždaviniui apie Karaliaučiaus tiltus
Apibendrindamas šį atskirą atvejį, Euleris sudaro tokio specialaus maršruto egzistavimo kriterijų: grafas turi būti jungus ir kiekviena jo viršūnė turi būti incidentinė lyginiam briaunų skaičiui. Grafas, pavaizduotas 2 piešinyje yra jungus, bet ne kiekviena jo viršūnė incidentinė lyginiam briaunų skaičiui.
1847 metais Kirchhofas išplėtė medžių teoriją tam, kad išspręstų tiesinių algebrinių lygčių sistemą, kuri leidžia rasti srovės jėgą kiekviename laide ir kiekvienoje elektros grandinėje.
Elektros schemų, kuriuose pavaizduotas srovės pasipriešinimas, kondensatoriai, induktyvumai ir t.t., nagrinėjimą jis pakeitė atitinkamų brėžinių (struktūrų), kuriuose buvo vaizduojamos tik viršūnės ir jungtys (briaunos arba lankai), nagrinėjimu, be to, nenurodydamas, kokius elektros elementus jungtys atitinka. Taip Kirchhofas pakeitė kiekvieną elektros grandinę ją atitinkančiu grafu ir parodė, jog tam, kad išspręstume atitinkamą lygčių sistemą, nebūtina nagrinėti atskirai kiekvieną elektros grandinės grafo ciklą. Vietoj to jis pasiūlė paprastą, bet efektyvų metodą (po to jis tapo standartiniu), pagal kurį pakanka nagrinėti tik paprastus grafo ciklus, apibrėžiamus bet kuriais iš jo pagrindinių pografių. 3 pieš. parodyta elektros grandinė N, ją atitinkantis grafas G ir pagrindinis pografis T.
3 pieš. Elektros grandinė N, jos grafas G ir jo pagrindinis pografis T
1857m. Keli (A.Cayley) atrado svarbią grafų grupę, vadinamą medžiais. Keli siekė perskaičiuoti prisotintųjų izomerų angliavandenilius Cn H2N+2 , kai duotas angliavandenilių atomų skaičius n (4 pieš.kai kurie iš jų).
4 pieš. Mažiausieji prisotintieji angliavandeniliai (iš kairės į dešinę metanas, etanas, propanas, butanas, izobutanas)
Keli pirmiausia suformulavo uždavinį abstrakčiai: rasti medžių su p viršūnių skaičių, kurių kiekvienos viršūnės laipsnis yra 1 arba 4. Jam nepavyko iškart išspęsti šio uždavinio ir jis pradėjo keisti sąlygą taip, kad būtų galima suskaičiuoti: a) šakninius medžius (kuriuose išskirta viena viršūnė); b) visus medžius; c) medžius, kurių viršūnių laipsnis neviršija 4 ir d) medžius, kurių viršūnių laipsnis yra 1 arba 4.
Vėliau Žordanas (1869m.), nepriklausomai nuo Keli, įvedė ir nagrinėjo medžius kaip matematinius objektus, ir, kaip rašė 1882m. Silvestras, jis padarė tai „visiškai neįtardamas, koks svarbus bus šis atradimas šiuolaikiniam chemijos mokslui”.
Žaidime, kurį 1859m. sugalvojo seras Viljamas Hamiltonas, panaudojamas dodekaedras, kuriame prie kiekvienos iš 20 viršūnių parašytas žinomo miesto pavadinimas. Žaidėjas turi apeiti „aplink pasaulį”, surasdamas tokį uždarą kelią, einantį per daugiakampio briaunas, kad kiekviena viršūnė būtų praeinama tik vieną kartą. Hamiltonas pardavė savo žaidimą vienam meistrui už 25 ginėjas; bet aprašytas žaidimas nedavė jokios finansinės naudos. Grafų teorijos kalba šis uždavinys formuluojamas taip: rasti Hamiltono ciklą dodekaedre (5 pieš.).
20
5 pieš. „Aplink pasaulį”
Grafo viršūnės sunumeruotos 1,2,…,20 (vietoje miestų pavadinimų), parodant pagrindinio ciklo egzistavimą. Benru atveju tai nėra išspręsta.
1936m. psichologas Levinas pasiūlė individo „gyvenimo erdvę” vaizduoti plokštuminio žemėlapio pagalba. Tokiame žemėlapyje sritys vaizduoja įvairius žmogaus užsiėmimus, pvz., ką jis daro darbe, namie, jo hobį:
6 pieš. Žemėlapis ir jį atitinkantis grafas
I.Grafų tipai
§1. Pagrindinės sąvokos
Daugelis autorių naudoja savo grafų teorijos terminologiją. Kai kurie autoriai apibrėžia „grafą” kaip grafą, kiti turi omeny tokius terminus kaip multigrafas, pseudografas, orientuotas grafas. Šiame darbe naudosime F.Charari [1] ir O.Ore [2] terminologiją.
Prieš pateikiant grafo apibrėžimą, parodysime 7 pieš. visus 11 grafų su keturiomis viršūnėmis. Vėliau pamatysime, kad :
1) bet koks grafas turintis 4 viršūnes izomorfiškas vienam iš jų;
2) penki grafai, į kairę nuo punktyrinės linijos, nesusieti;
3) šeši grafai, į dešinę nuo punktyrinės linijos, susieti;
4) paskutinis grafas – pilnas;
5) pirmas grafas – tuščias arba visiškai nesusietas;
6) pirmas grafas su keturiomis briaunomis – ciklas; 7)pirmas grafas su trimis briaunomis – paprasta grandinė.
7 pieš. Grafai su keturiomis viršūnėmis
Grafas G sudarytas iš baigtinės aibės V, turinčios p viršūnių ir aibės X, turinčios q nesutvarkytų porų įvairių viršūnių iš V. Kiekvieną porą x={u,v} viršūnių aibėje X vadiname grafo G briauna ir sakome, kad ji jungia viršūnes u ir v (kartais tai žymima u adj v); viršūnė u ir briauna x yra incidentinės, taip pat kaip ir v su x. Jeigu dvi skirtingos briaunos x ir y incidentinės tai pačiai viršūnei, tai jos vadinamos jungtinėmis. Grafas, turintis p viršūnių ir q briaunų vadinamas (p,q)-grafu. (1,0)-grafas vadinamas trivialiuoju.
8 piešinyje grafo G viršūnės u ir v jungtinės, o viršūnės u ir w ne; briaunos x ir y jungtinės, o x ir z ne. Nors diagramoje briaunos x ir z susikerta, bet jų susikirtimo taškas nėra viršūnė.
8 pieš. Grafas, iliustruojantis jungumą
Multigrafe negali būti kilpų, t.y. briaunų, jungiančių viršūnes pačias su savimi, bet viršūnių poros gali būti sujungtos daugiau negu viena briauna. Šios briaunos vadinamos kartotinėmis. Jei galimos kilpos ir kartotinės briaunos, tai grafas vadinamas pseudografu.
9 pieš. Multigrafas ir pseudografas
9 piešinyje pavaizduotas multigrafas ir pseudografas, kurių pagrindą sudaro tas pats grafas -keturkampis. Taigi, Karaliaučiaus tiltų uždavinyje grafas – tai multigrafas.
Orientuotu grafu vadiname grafą D, sudarytą iš baigtinės aibės viršūnių V ir duoto skaičiaus sutvarkytų viršūnių porų aibės X. Elementai iš X vadinami orientuotomis briaunomis arba lankais.
10 pieš. Orientuotas grafas
Grafas vadinamas žymėtu, jei jo viršūnės skiriasi viena nuo kitos kokiais nors žymenimis, pvz.: v1, v2,…,vp. Grafai G1 ir G2 11 pieš. žymėti, o grafas G3 – ne.
11 pieš. Pažymėti ir nepažymėti grafai
Grafo G pografiu vadinamas grafas, kurio visos viršūnės ir briaunos priklauso grafui G. Jei G1 – grafo G pografis, tai G vadinamas grafo G1 viršgrafiu.
12 pieš. Grafas ir jo pografiai
Pagrindinis pografis – tai grafo G pografis, turintis visas grafo G viršūnes. Pašalinę viršūnę vi iš grafo G, gausime grafo G pografį G-vi be viršūnės vi ir be visų briaunų incidentinių viršūnei vi. Kitaip tariant, G – vi yra maksimalus grafo G pografis, neturintis viršūnės vi. Pašalinę briauną xj iš G, gausime pagrindinį pografį G-Xj, turintį visas grafo G briaunas, išskyrus xj, t.y. G- xj yra maksimalus grafo G pografis, kuriam nepriklauso xj. Norimo kiekio viršūnių arba briaunų iš G pašalinimas apibrėžiamas kaip nuoseklus visų šių elementų pašalinimas iš aibių V ir X.
Iš kitos pusės, jei vi ir vj nėra jungtinės grafe G, tai pridėję briauną vivj gausime mažiausią grafo G viršgrafį, turintį briauną vivj. Šios sąvokos pavaizduotos 13 piešinyje.
Yra grafų, kuriems G-v (ar G-x) nepriklauso nuo to, kurią viršūnę (ar briauną) pašalinsime (pridėsime):
14 pieš. Grafas G ir grafai, gauti pašalinus viršūnę, pašalinus (pridėjus) briauną iš G.
Du grafai G ir H vadinami izomorfiniais, jei tarp jų viršūnių aibių egzistuoja abipus vienareikšmė atitiktis, išlaikanti jungumą. Pastebėsime, kad izomorfizmas grafų teorijoje vaidina ekvivalentumo vaidmenį.
15 pieš. izomorfiniai grafai G1 ir G2
Pilnuoju grafu Kp vadinsime grafą, kurio kiekviena viršūnių pora yra jungtinė.
Dvipusis grafas G – tai grafas, kurio viršiūnių aibę V galima išskaidyti į du poaibius V1 ir V2 taip, kad kiekviena grafo G briauna jungia viršūnes iš skirtingų aibių (sakysime, kad grafo G briaunos jungia viršūnių aibes V1 ir V2).
Jei grafas G turi visas briaunas, kurios jungia aibes V1 ir V2, tai toks grafas vadinamas pilnu dvipusiu grafu ir žymimas Km>n. Žvaigžde vadiname pilną dvipusį grafą K1n.
16a piešinyje pavaizduotas grafas, kuris yra izomorfinis 16b piešinio dvipusiam grafui.
16 pieš. Grafas, izomorfinis dvipusiam grafui K33
Grafo G papildiniu G vadiname grafą, kurio viršūnės yra jungtinės tada ir tik tada, kai jos nėra jungtinės grafe G. Viršūnių aibės sutampa. Grafai Kp visiškai nejungūs (arba jungūs laipsniu 0).
§2. Maršrutai ir jungumas
Viena iš paprasčiausių grafų savybių – jungumas. Šiame skyriuje panagrinėsime pagrindines struktūrines jungių ir nejungių grafų savybes.
Maršrutu grafe G vadiname sutvarkytą seką viršūnių ir briaunų v0, x1, v1,…,vn-1, xn, vn; ši seka prasideda ir baigiasi viršūne ir kiekviena sekos briauna incidentinė dviems viršūnėms, viena iš kurių eina prieš šią briauną, o kita eina po jos. Nurodytas maršrutas jungia viršūnes v0 ir vn, ir jį galima užrašyti v0v1v2…vn (nežymint briaunų). Šis eiliškumas kartais vadinamas (v0-vn) – maršrutu.
Maršrutas yra uždaras, jei v0=vn ir atviras priešingu atveju. Maršrutas vadinamas grandine, jei visos jo briaunos skirtingos ir paprasta grandine, jeigu visos jo viršūnės (o taip pat briaunos) skirtingos. Uždara grandinė vadinama ciklu. Uždaras maršrutas vadinamas paprastu ciklu C„, jei visos jo n viršūnių skirtingos ir n>3. C3 vadinamas trikampiu.
Grafe G (18 pieš.) v1v2v5v2v3 – maršrutas, kuris nėra grandinė, o v1v2v5v4v2v3 – grandinė, v1v2v5v4 – paprasta grandinė, v2v4v5v2 – paprastas ciklas.
18 pieš. Maršrutai
Grafas G vadinamas jungiu, jei bet kuri jo viršūnių pora sujungta paprasta grandine. Maksimalus grafo G jungus pografis vadinamas jungumo komponente arba tiesiog grafo G komponente.
Taigi, nejungus grafas turi bent dvi komponentes. Grafas 19 pieš. turi 10 komponenčių.
19 pieš.Grafas su 10 komponenčių.
Atstumu d(u,v) tarp dviejų grafo G viršūnių uirv vadinamas trumpiausios paprastos grandinės ilgis, jungiančios jas; jei u ir v nėra sujungtos, tai tariame, kad d(u,v)=oo. Jungiame grafe atstumas tai metrika, t.y. tenkina metrikos aksiomas: bet kokioms trims viršūnėms u,v ir w:
1) d(u,v) >0 ir d(u,v)=0 tada ir tik tada, kai u=v;
2) d(u,v)=d(v,u);
3) d(u,v)+d(v,w) >d(u,w).
Trumpiausia paprasta (u-v)-grandinė dažnai vadinama geodezine. Jungaus grafo G skersmeniu d(G) vadiname pačios ilgiausios geodezinės ilgį.
§3. Reguliarus grafai
Viršūnės vi grafe G laipsniu – žymima di arba deg vi – vadiname briaunų incidentinių su vi skaičių. Kadangi kiekviena briauna incidentinė dviem viršūnėm, tai į viršūnės laipsnių sumą kiekviena briauna įtneša dvejetą. Iš čia seka tvirtinimas, kurį suformulavo Euleris, ir kuris yra pirmoji istorinė grafų teorijos teorema.
4.1Teorema: Grafo G viršūnių laipsnių suma yra lygi dvigubam briaunų skaičiui:
Z deg v’ =2q.
i
1 Išvada: Kiekviename grafe viršūnių su nelyginiais laipsniais skaičius yra lyginis. Minimalų grafo G viršūnių laipsnį žymime min deg G arba 5(G), maksimalų – max deg G=A(G).
Jei 8(G) =A(G) =r, tai visos viršūnės turi vienodą laipsnį ir toks grafas G vadinamas reguliariu laipsnio r grafu. Šiuo atveju deg G=r. Viršūnė v vadinama izoliuotąja, jei deg v=0 ir galine (arba kabančia), jei deg v=1.
Reguliarus 0 laipsnio grafas neturi briaunų. Jei G – reguliarus 1 laipsnio grafas, tai kiekviena jo komponentė turi vieną briauną; reguliariajame 2 laipsnio grafe kiekviena komponentė yra ciklas. Pirmi įdomūs reguliarūs grafai yra 3-čio laipsnio; tokie grafai vadinami kubiniais.
20 piešinyje parodyti du reguliarūs grafai su 8 viršūnėmis.
20 pieš. Kubiniai grafai su 8 viršūnėmis
2 Išvada: Kiekvienas kubinis grafas turi lyginį viršūnių skaičių. Yra žinomas toks galvosūkis, vadinamas Ramzio uždaviniu:
Įrodyti, kad tarp bet kokių šešių žmonių atsiras arba trys poromis pažįstami arba trys poromis nepažįstami.
Nurodytą situaciją galima aprašyti grafu G su šešiomis viršūnėmis, vaizduojančiomis žmones; dviejų viršūnių jungumas reiškia, kad žmonės pažįstami. Reikia parodyti, kad grafe G atsiras arba trys poromis jungios arba nejungios viršūnės.
3.2 Teorema: Jei G – grafas su šešiomis viršūnėmis, tai arba G, arba G turi savyje trikampį. Įrodymas:
Tegu v – bet kuri viršūnė grafo G, kuris turi šešias viršūnes. Kadangi viršūnė v su bet kokia
iš likusių penkių viršūnių jungi arba grafe G arba G , tai, neprarandant bendrumo, tarkime, kad viršūnės u1, u2, u3 jungios su v grafe G. Jei bet kokios dvi iš viršūnių u1, u2, u3 jungios grafe G, tai
su viršūne v jos sudaro trikampį. Jei jokios dvi iš jų nėra jungios grafe G, tai grafe G viršūnės u1, u2, u3 sudaro trikampį.
Apibendrinant 3.2 teoremą, kyla klausimas: koks mažiausias sveikas skaičius r(m,n), kad grafas su r(m,n) viršūnėmis turi savyje Km arba Kn ?
Skaičiai r(m,n) vadinami Ramzio skaičiais. Aišku, kad r(m,n) =r(n,m). Uždavinys, susijęs su Ramzio skaičių radimu, lieka neišspręstas, nors yra žinomas toks įvertinimas, kurį gavo Erdos ir Szekeres:
§4. Veiksmai su grafais
Tegu grafai G1 ir G2 turi nesikertančias viršūnių aibes V1 ir V2 ir nesikertančias briaunų aibes X1 ir X2. Tokių grafų sąjunga G1UG2 vadinamas grafas, kurio viršūnių aibė V=V1UV2, o briaunų aibė X=X1UX2. Grafų suma žymima G1+G2 ir susideda iš G1UG2 bei visų briaunų,
jungiančių aibes V1 ir V2. Pavyzdžiui, Km>n= Km + Kn . Šios operacijos yra pavaizduotos 22 pieš. kur
G1=K1,2=P3 ir G2=P4.
Jei G – jungus grafas, tai nG žymi grafą su n komponentėmis, kurių kiekviena izomorfinė G. Kiekvieną grafą galima užrašyti pavidalu UiniGi, kur Gi skiriasi nuo Gj, kai i^j. Pavyzdžiui, nejungų grafą pavaizduotą 19 piešinyje, galima užrašyti taip: 4K1U3K2U2K3UK1;2.
22 pieš. Grafų sąjunga ir sudėtis
Yra kelios operacijos su grafais G1 ir G2, kurios sudaro grafą G su viršūnių aibe, lygia Dekarto sandaugai V1xV2. Tarp jų – sandauga (arba Dekarto sandauga) bei kompozicija.
Kad galėtume apibrėžti grafų G1 ir G2 sandaugą G1xG2, panagrinėkime bet kokias dvi viršūnes u=(u1,u2) ir v=(v1,v2) iš V=V1xV2. Viršūnės u ir v bus jungtinės grafe G1xG2 tada ir tik tada, kai [ u1=v1 ir u2 adj v2] arba [u2=v2 ir u1adj v1]. Grafų G1=P2 ir G2=P3 sandauga pavaizduota 23 piešinyje.
23 pieš. Grafų sandauga
Grafo G kvadratas G2 turi tą pačią viršūnių aibę kaip ir grafas G, t.y. V(G2)=V(G) ir dvi viršūnės u ir v grafe G2 jungtinės tada ir tik tada, kai d(u,v)<2 grafe G. Grafo G laipsniai G3, G4,.. apibrėžiami analogiškai. Pavyzdžiui: C52=K5 ir P42=K4-x.
Jei G1 ir G2 - (p1, q1) ir (p2, q2) - grafai, tai kiekvienai iš anksčiau apibrėžtų operacijų galima rasti gaunamo grafo viršūnių skaičių ir briaunų skaičių (1 lentelė).
§5. Sujungimo taškai, tiltai bei blokai
Grafo G sujungimo tašku vadinama viršūnė, kurią pašalinus, padidėja grafo G komponenčių skaičius. Briauna, kurios pašalinimas padidina komponenčių skaičių, vadinama tiltu. Jei v - jungaus grafo G sujungimo taškas, tai grafas G-v nėra jungus. Nedaliu grafu vadinamas jungus, netuščias, neturintis sujungimo taškų grafas. Grafo blokas - tai jo maksimalus nedalus pografis. Jei G -nedalus grafas, tai dažnai jis pats vadinamas bloku.
24 pieš. Grafas ir jo blokai
24 piešinyje: v - sujungimo taškas, o w - ne, x - tiltas, o y - ne; B1, B2, B3, B4 - grafo G
blokai.
Kiekviena grafo briauna priklauso tik vienam iš jo blokų, taip pat kaip ir kiekviena viršūnė, kuri nėra nei izoliuota, nei sujungimo taškas. Grafo G bet kokio paprasto ciklo briaunos taip pat priklauso tik vienam blokui. Būtent todėl grafo blokai išskaido jo briaunas ir paprastus ciklus į aibes, kurias galima nagrinėti kaip briaunų aibes.
5.1 Teorema: Tegu v - jungaus grafo G viršūnė. Tuomet ekvivalentūs tokie teiginiai:
1) v - sujungimo taškas grafe G;
2) egzistuoja tokios viršūnės u ir w, nesutampančios su v, kad v priklauso bet kuriai paprastai (u,w) - grandinei;
3) egzistuoja viršūnių aibės V-{v} išskaidymas į tokius du poaibius U ir W, kad bet kokioms viršūnėms u G U ir WG W, viršūnė v priklauso bet kuriai paprastai (u-w) -grandinei.
5.2 Teorema: Tegu x - jungaus grafo G briauna. Tuomet yra ekvivalentūs tokie tvirtinimai:
1) x - grafo G tiltas;
2) x nepriklauso nei vienam grafo G paprastam ciklui;
3) grafe G egzistuoja tokios viršūnės u ir v, kad briauna x prilkauso bet kokiai paprastai grandinei, kuri jungia u ir v;
4) egzistuoja aibės V išskaidymas į tokius poaibius U ir W, kad bet kokioms viršūnėms u G U ir WG W, briauna x priklauso bet kokiai paprastai (u-w) - grandinei.
5.3 Teorema: Tegu G - jungus grafas su ne mažiau kaip trimis viršūnėmis. Tuomet yra ekvivalentūs tokie teiginiai:
1) G - blokas;
2) bet kokios dvi grafo G viršūnės priklauso tam tikram bendram paprastam ciklui;
3) bet kokia viršūnė ir bet kokia briauna grafe G priklauso tam tikram bendram paprastam ciklui;
4) bet kokios dvi grafo G briaunos priklauso tam tikram bendram paprastam ciklui;
5) bet kokioms dviem grafo G viršūnėms ir bet kokiai briaunai, egzistuoja paprasta grandinė, jungianti tas viršūnes, kuriai priklauso duotoji briauna;
6) bet kokioms trims skirtingoms grafo G viršūnėms egzistuoja paprasta grandinė, jungianti dvi iš jų ir einanti per trečiąją;
7) kiekvienoms trims skirtingoms grafo G viršūnėms egzistuoja paprasta grandinė, jungianti dvi iš jų ir neinanti per trečiąją.
5.4Teorema: Bet kokiame netrivialiame jungiame grafe atsiras bent dvi viršūnės, nesančios sujungimo taškais.
Įrodymas:
Tegu u ir v - grafo G viršūnės maksimaliai nutolusios viena nuo kitos, t.y. tokios, kad d(u,v)=d(G). Tarkime, kad v - sujungimo taškas. Tuomet egzistuoja viršūnė w, priklausanti tai grafo G-v komponentei, kuriai nepriklauso viršūnė u. Reiškia, v priklauso bet kokiai grandinei, jungiančiai u ir v ir todėl d(u,w)>d(u,v), kas yra neįmanoma. Gavome, kad nei viršūnė v, nei viršūnė u nėra grafo G sujungimo taškai.
Grafo G blokų grafu B(G) vadinamas grafas, kurio viršūnės yra grafo G blokai ir dvi viršūnės grafe B(G) yra jungtinės tada ir tik tada, kai atitinkantys jas grafo G blokai turi bendrą sujungimo tašką. Grafo G sujungimo taškų grafu C(G) vadinamas grafas, kurio viršūnių aibė sutampa su grafo G sujungimo taškų aibe, o dvi viršūnės jungtinės tada ir tik tada, kai jas atitinkantys grafo G sujungimo taškai priklauso vienam blokui. Reikia pastebėti, kad C(G) apibrėžiamas tik grafams G, kurie turi nors vieną sujungimo tašką. Šios sąvokos iliustruojamos 25 piešinyje.
5.5 Teorema: Grafas H yra blokų grafas kažkuriam grafui tada ir tik tada, kai kiekvienas grafo H blokas – pilnas grafas. Įrodymas:
Tegu H=B(G); tarkime, kad grafe H yra blokas Hi, kuris nėra pilnas grafas. Tuomet Hi atsiras pora nejungių viršūnių, priklausančių vienam paprastam ciklui Z, kurio ilgis ne mažesnis už 4.Iš čia seka, kad grafo G blokų sąjunga, atitinkanti viršūnes iš Hi, kurios priklauso Z, yra jungus grafas, kuris neturi sujungimo taškų, t.y. ši sąjunga priklauso kažkokiam blokui, kas prieštarauja blokų maksimalumo savybei.
Tegu dabar H – grafas, kuriame kiekvienas blokas – pilnas grafas. Sudarome grafą B(H), o po to naują grafą G, pridėdami kiekvienai grafo B(H) viršūnei Hi kažkokį baigtinį skaičių briaunų, lygų tų bloko Hi viršūnių skaičiui, kurios nėra grafo H sujungimo taškai. Matome, kad grafas B(G) izomorfiškas H.
§6. Medžiai
Yra vienas paprastas ir svarbus grafų tipas, kuriam skirtingi autoriai davė vienodą pavadinimą – medžiai. Medžiai svarbūs ne tik savo taikomąja verte, bet ir savo vieta grafų teorijoje. Dažnai sprendžiant kažkokią problemą ji pirmiausia yra formuluojama medžiams. Pavyzdžiui, Ulamo hipotezė.
Ulamo hipotezė. Tegu grafas G turi p viršūnių vi, grafas H turi p viršūnių ui ir p>3. Jei kiekvienam i pografiai Gi=G-vi ir Hi=H-ui izomorfiški, tai ir grafai G ir H izomorfiški.
Grafas vadinamas acikliniu, jei jis neturi ciklų. Medis – tai jungus aciklinis grafas. Pavyzdžiui, egzistuoja 23 skirtingi medžiai su aštuoniomis viršūnėmis (26 piešinyje keli iš jų):
26 pieš. 10 medžių su 8 višūnėmis
6.1 Teorema: Grafui G ekvivalentūs tokie teiginiai:
1) G – medis;
2) bet kurios dvi viršūnės grafe G sujungtos vienintele paprasta grandine;
3) G – jungus grafas ir p=q+1;
4) G – aciklinis grafas ir p=q+1;
5) G – aciklinis grafas, ir jeigu bet kokią porą nejungių viršūnių sujungti briauna x, tai grafe G+x bus tik vienas paprastas ciklas;
6) G – jungus grafas, nesutampantis su Kp, kai p>3, ir jeigu bet kokią porą nejungių viršūnių sujungti briauna x, tai grafe G+x bus tik vienas paprastas ciklas;
7) G – grafas, nesutampantis su K3UK1 ir K3UK2, p=q+1 ir jeigu bet kokią porą nejungių viršūnių sujungti briauna x, tai grafe G+x bus tik vienas paprastas ciklas.
1 Išvada: Bet kokiame netrivialiame medyje yra bent dvi kabančios viršūnės.
Viršūnės v ekscentricitetu e(v) jungiame grafe G vadiname max d(u,v) pagal visas viršūnes u grafe G. Spinduliu r(G) vadiname mažiausią ekscentricitetą. Pastebėsime, kad didžiausias iš ekscentricitetų yra lygus grafo skersmeniui.
Viršūnė v vadinama centrine grafo G viršūne, jei e(v) =r(G); grafo G centras – tai visų centrinių viršūnių aibė. 27 piešinyje pavaizduotas medis, kuriame nurodytas kiekvienos viršūnės ekscentricitetas. Šio medžio skersmuo – 7, radianas – 4, o jo centras tai viršūnės u ir v, kurių ekscentricitetas 4.
§7. Jungumas ir briauninis jungumas
Grafo G jungumu x=X(G) vadinamas mažiausias viršūnių skaičius, kurias pašalinus
gauname nejungų arba trivialų grafą. Iš apibrėžimo seka, kad nejungaus grafo jungumas lygus 0, o jungaus grafo, turinčio sujungimo tašką, jungumas lygus 1. Pilno grafo Kp negalima padaryti nejungiu, kad ir kiek jo viršūnių pašalintume, o tirvialų grafą gauname pašalinę iš Kp p-1 viršūnę; todėl x(Kp) =p-1. Kartais x vadinamas viršūnių jungumu.
Grafo G briauniniu jungumu X=X(G) vadiname mažiausią briaunų skaičių, kurias pašalinę gauname nejungų arba trivialų grafą. Aišku, kad X(K1) =0, ir nejungaus grafo briauninis jungumas lygus 0, o jungaus grafo, turinčio tiltą, briauninis jungumas lygus 1. Jungumas x(G), briauninis jungumas X(G) ir mažiausias grafo laipsnis 8(G) susieti nelygybe, kurią atrado Whitney. 7.1 Teorema: Bet kokiam grafui G:
X(G)
Pavyzdžiui, jei G – reguliarus laipsnio r>p/2 grafas, tai X(G) =r. Be to, X(Kp) =p-1.
Pasakyti to paties apie viršūnių jungumą kaip 7.3 teoremoje negalima.
Grafas G vadinamas n-jungiu, jei x(G)>n. Pastebėsime, kad netrivialus grafas 1-jungus tada ir tik tada, kai jis jungus ir 2-jungus tada ir tik tada, kai jis yra blokas, turintis daugiau negu viena briauną. Todėl grafas K2 – vienintelis blokas nesantis 2-jungus. Iš 6.3 teoremos seka, kad grafas 2-jungus tada ir tik tada, kai kiekvienos dvi jo viršūnės priklauso bet kokiam jo paprastam ciklui.
7.4 Teorema: Jeigu grafas G n-jungus, n>2, tai bet kokia aibė turinti n grafo G viršūnių, priklauso paprastam ciklui.
Jei paimsime ciklą Cn, tai matome, kad atvirkščias teiginys nėra teisingas, kai n>2. Tam, kad apibrėžtume 3-jungų grafą, turime pasinaudoti grafo, vadinamo „ratu”, sąvoka, kurią įvedė Tattas. Kai n>4, ratas Wn apibrėžiamas kaip grafas K1+Cn-1 (29 pieš.).
II. Kai kurios briauninių grafų savybės