Grafai kaip viršūnių ir briaunų tinklai

Pradėkite nuo keturių kambarių ir trijų tiesioginių jungčių

Keturi kambariai pažymėti A, B, C ir D. Viena tiesioginė jungtis jungia A su B, kita – A su C, o trečia – B su C. Su D nesujungta nė viena jungtis. Kurie kambariai turi tiesioginę jungtį su A? Kiek atskirų jungčių aprašėme?

Kiekvienam kambariui nubrėžkite po pažymėtą tašką, o kiekvienai išvardytai jungčiai – po liniją. A tiesiogiai sujungtas su dviem kambariais: B ir C. Iš viso yra trys jungtys. D vis tiek priklauso mūsų kambarių rinkiniui, nors su juo nesujungta nė viena linija. Brėžinyje išsaugoma informacija apie ryšius, bet nevaizduojami kambarių dydžiai ir jungčių ilgiai.

Pasirengimui pakanka mokėti kiekvieną objektą suskaičiuoti vieną kartą ir sudėti sveikuosius skaičius, gautus skaičiuojant. Nuorodoje pateikta vaizdavimo būdų pamoka padeda palyginti paveikslą su jo lentele. Grafų teorijos žinių nereikia. Skaitydami pirmą kartą, sekite kambarių paveikslą, briaunų lentelę ir laipsnių skaičiavimą, tada – įrodymą, paremtą dviem briaunos galais. Prie matricų ir rodyklių grįžkite, kai šias idėjas gerai suprasite.

Įvardykite objektus ir ryšius

Viršūnė – tai vienas tinklo objektas, vaizduojamas pažymėtu tašku. Šio žodžio daugiskaita – viršūnės. Briauna – tai viena jungtis tarp dviejų galų. Baigtinė viršūnių aibė vadinama V, o baigtinė briaunų aibė – E. Žymenys |V| ir |E| reiškia atitinkamai viršūnių ir briaunų skaičių.

Dvi viršūnės yra gretimos, kai jas tiesiogiai jungia briauna. Briauna yra incidentiška viršūnei, kai ta viršūnė yra briaunos galas. Kambarių tinkle A ir B yra gretimos, o briauna A–B yra incidentiška ir A, ir B. D yra izoliuota: jokia briauna neturi galo D.

Neorientuota briauna neturi pasirinktos krypties: jungtis A–B yra ta pati briauna kaip B–A. Tai nieko nesako apie fizinį judėjimą, kol modelyje nenurodyta, ką reiškia jungtis. Ryšys gali reikšti draugystę, kabelį arba leidžiamą palyginimą. Prieš interpretuodami grafą, pasirinkite ryšio reikšmę.

Briauna turi du galus. Jie gali būti dviejose skirtingose viršūnėse arba, kai leidžiama kilpa, abu toje pačioje viršūnėje. Mūsų grafai yra baigtiniai. Aiškiai leidžiame, kad V būtų tuščia; tuomet E taip pat turi būti tuščia, nes kiekvienai briaunai reikia nurodytų galų. Kai V netuščia, o E tuščia, visos viršūnės tiesiog lieka izoliuotos.

Pakeiskite brėžinį, nekeisdami tinklo

Perkelkite A, B, C ir D arba išlenkite tris kambarių tinklo briaunas. Jei viršūnių žymos ir kiekvienos briaunos galai lieka tie patys, žymėtas tinklas nesikeičia. Brėžinyje pavaizduotas briaunos ilgis, susikirtimas ir trikampio vidaus plotas nėra papildomi šio nesvertinio grafo duomenys.

Susikirtimo pavyzdyje briaunos A–C ir B–D susikerta, tačiau susikirtimo vietoje nėra viršūnę žyminčio taško. Modelyje yra keturios viršūnės ir dvi briaunos. Susikirtimas nesukuria jokios jungties tarp briaunų. Jei toje vietoje sąmoningai pridėsite naują viršūnę E ir dvi briaunas pakeisite briaunomis A–E, E–C, B–E ir E–D, gausite kitą tinklą su penkiomis viršūnėmis ir keturiomis briaunomis.

Šalia viršūnės einanti linija nėra jai incidentiška, nebent ta viršūnė nurodyta kaip briaunos galas. Kai brėžinys dviprasmiškas, lemiamą reikšmę turi briaunų galų lentelė. Perbraižymas yra naudingas patikrinimo būdas: užuot sprendę vien pagal formą, palyginkite išsamius briaunų galų sąrašus, įtraukdami ir izoliuotas viršūnes.

Viršūnių pavadinimus taip pat galima nuosekliai pakeisti. Abipus vienareikšmė visų viršūnių atitiktis, išsauganti kiekvieną briauną ir jos kartotinumą, yra struktūros peržymėjimas. Čia lygindami brėžinius žymų nekeičiame; vien to, kad viršūnių ir briaunų skaičiai sutampa, nepakanka tam pačiam žymėtam tinklui nustatyti.

Nurodykite, kokias briaunas leidžia modelis

Paprastasis neorientuotas grafas neturi kilpų ir lygiagrečių briaunų. Kilpa jungia viršūnę su ja pačia. Lygiagrečios briaunos yra skirtingos briaunos, turinčios tą pačią nesutvarkytą galų porą. Todėl paprastajame grafe kiekvieną briauną galima užrašyti kaip dviejų elementų aibę, pavyzdžiui, {A,B}; užrašas {B,A} apibūdina tą pačią briauną.

Du skirtingi kabeliai tarp A ir B yra dvi briaunos, nors jų galai sutampa. Joms suteikiame identifikatorius e1 ir e2, užuot išsaugoję {A,B} tik vieną kartą ir praradę vieną kabelį. Bendresniu atveju čia neorientuotas multigrafas leidžia kilpas ir lygiagrečias briaunas: kiekviena identifikatorių turinti briauna turi du galus, kurių tvarka nesvarbi, o pasikartojimas leidžiamas.

Pavyzdžiui, e1 ir e2 jungia A su B, e3 jungia B su C, o e4 yra kilpa ties A. D tebėra nurodyta ir izoliuota. Grafas turi keturias viršūnes ir keturias briaunas. Kilpa yra viena briauna, kurios abu galai yra ties A; tai nėra dvi skirtingos briaunos.

Patikrinkite, kokios terminijos laikomasi kituose šaltiniuose: kai kuriuose multigrafu vadinamas grafas su lygiagrečiomis briaunomis, o kai leidžiamos kilpos, vartojamas terminas „pseudografas“. Čia reikšmę apibrėžia aiškiai nurodytos briaunų galų taisyklės. Sujungus lygiagrečias briaunas į vieną arba pašalinus kilpas, modelis pasikeičia; skaičiuojant jungtis to negalima daryti nepaminėjus.

Viršūnės laipsnis – briaunų galų skaičius

Neorientuotajame grafe viršūnės v laipsnis deg(v) yra briaunų galų ties v skaičius. Kiekviena įprasta briauna kiekvienos savo galinės viršūnės laipsnį padidina vienetu. Kilpa savo vienintelės viršūnės laipsnį padidina dviem, nes abu jos galai yra ties ta viršūne. Kiekviena lygiagreti briauna skaičiuojama atskirai.

Paprastajame kambarių grafe deg(A)=2, deg(B)=2, deg(C)=2 ir deg(D)=0. Paprastajame grafe laipsnis taip pat lygus skirtingų gretimų viršūnių skaičiui. Multigrafe toks trumpesnis skaičiavimo būdas netinka: dvi lygiagrečios A–B briaunos ties A turi du briaunų galus, bet tik vieną skirtingą kitą gretimą viršūnę.

Keturių briaunų multigrafe ties A yra po vieną e1 ir e2 galą ir du jos kilpos e4 galai, todėl deg(A)=4. Ties B yra po vieną e1, e2 ir e3 galą, todėl deg(B)=3. C laipsnis yra 1, o D laipsnis yra 0. Laipsnių suma lygi 8. Jei leidžiame viršūnei dėl kilpos būti gretimai pačiai sau, vienintelės skirtingos A gretimos viršūnės yra A ir B.

Incidencijos lentelės eilutės atitinka viršūnes, o stulpeliai – atskirai pažymėtas briaunas. Įrašas nurodo tos briaunos galų ties ta viršūne skaičių: 0, 1 arba 2. Kiekvieno stulpelio įrašų suma lygi 2; kiekvienos eilutės įrašų suma lygi tos viršūnės laipsniui. Pagal šią taisyklę kilpos užrašomos nepraleidžiant nė vieno jų galo.

Laipsnių sumos formulės įrodymas skaičiuojant tuos pačius galus

Kiekviename baigtiniame neorientuotajame grafe, laikantis nurodytos kilpų skaičiavimo taisyklės, visų viršūnių laipsnių suma lygi 2|E|. Sumos ženklas Σ reiškia, kad sudedama po vieną narį kiekvienai viršūnei, taigi Σ(v∈V)deg(v)=2|E|. Dešinėje pusėje kiekvienai briaunai skaičiuojami du jos galai.

Norėdami tai įrodyti, kiekvienai briaunai ir jos pirmojo arba antrojo galo pasirinkimui sudarykite po vieną skaičiavimo vienetą. Net kilpa duoda du atskirus vienetus, susietus su ta pačia viršūne. Skaičiuojant pagal briaunas gaunama 2|E| vienetų. Sugrupavus tuos pačius vienetus pagal viršūnę, su kuria jie susieti, viršūnės v grupėje gaunama deg(v) vienetų. Grupės nepersidengia ir apima visus vienetus, todėl bendras jų skaičius lygus laipsnių sumai.

Įrodymas tinka lygiagrečioms briaunoms, nes jos yra atskiros briaunos. Jis tinka ir tada, kai briaunų nėra: kiekvienos viršūnės laipsnis yra 0, o abu bendrieji skaičiai yra 0. Kai V tuščia, suma neturi narių ir pagal apibrėžimą lygi 0, o tai vėl atitinka |E|=0. Baigtinumas leidžia naudoti šiuos įprastus sveikuosius bendruosius skaičius.

Pavadinimas „rankų paspaudimų lema“ primena žmones, spaudžiančius vieni kitiems rankas: kiekvienas rankų paspaudimas kiekvieno iš dviejų žmonių skaičių padidina vienetu. Tikrų rankų paspaudimų modelyje paprastai nenumatoma, kad žmogus spaustų ranką pats sau; kilpos yra atskiras matematinis išplėtimas, kuriam taikoma dviejų galų taisyklė. Diagrama patvirtina vieną nedidelį atvejį, o skaičiavimu grindžiamas argumentas įrodo formulę kiekvienam baigtiniam atvejui.

Laipsnių sumos patikrai ir jų ribotumai

Laipsnių suma yra lyginė, nes ji lygi dvigubam sveikajam skaičiui. Lyginių laipsnių suma yra lyginė; suporavus nelyginio laipsnio vienetus, vienas vienetas lieka be poros. Taigi laipsnių sumos lyginumas sutampa su nelyginio laipsnio viršūnių skaičiaus lyginumu. Šis skaičius turi būti lyginis.

Keturias briaunas turinčio multigrafo laipsniai yra 4,3,1,0, ir jame yra lygiai dvi nelyginio laipsnio viršūnės. Grafas su viena kilpa turi laipsnį 2 ir neturi nelyginio laipsnio viršūnių. Siūlomo neorientuotojo grafo, kurio laipsniai būtų 2,2,1, laipsnių suma būtų nelyginė 5, todėl pagal šiuos susitarimus toks grafas neegzistuoja.

Lyginė laipsnių suma yra būtina, bet nepakankama siūlomo paprastojo grafo egzistavimo sąlyga. Keturių viršūnių laipsnių 3,3,1,1 suma yra 8, o kiekvienas laipsnis neviršija 3, tačiau toks grafas neįmanomas. Kiekviena viršūnė, kurios laipsnis 3, turi būti gretima visoms kitoms viršūnėms; tuomet kiekviena likusi viršūnė jau turi bent dvi kaimynes, o tai prieštarauja laipsniui 1.

Laipsniai taip pat neapibrėžia viso tinklo su pažymėtomis viršūnėmis. Briaunos A–B ir C–D kiekvienai viršūnei suteikia laipsnį 1. Kitos briaunos A–C ir B–D taip pat kiekvienai viršūnei suteikia laipsnį 1. Galinių viršūnių lentelės leidžia šiuos tinklus atskirti. Laipsnių suma yra patikima suderinamumo patikra, bet ji nepakeičia duomenų apie jungtis.

Gretimumo lentelės skaitymas pagal aiškų susitarimą

Paprastojo neorientuotojo grafo gretimumo matrica yra kvadratinė lentelė, kurios eilutės ir stulpeliai pažymėti tomis pačiomis viršūnių žymėmis. Eilutėje u ir stulpelyje v įrašykite 1, kai u ir v yra gretimos, o kitu atveju – 0. Jos įstrižainės elementai yra 0, nes kilpos neleidžiamos. Ji simetrinė: elementas u,v lygus elementui v,u.

Kiekvienos eilutės suma lygi atitinkamos viršūnės laipsniui. Kambarių matricoje pozicijoje A,B yra 1, o pozicijoje B,A – dar vienas toks elementas. Šie du elementai žymi du vienos neorientuotosios briaunos galus, o ne dvi briaunas. Todėl visų elementų suma yra 2|E|, o padalijus šią sumą iš 2 gaunamas briaunų skaičius.

Šios pamokos multigrafų lentelėms aiškiai išplečiame susitarimą: ne įstrižainėje esantis elementas u,v yra briaunų, jungiančių u ir v, skaičius; įstrižainės elementas v,v yra dvigubas kilpų ties v skaičius. Šioje simetrinėje lentelėje kiekvienos eilutės suma tebėra viršūnės laipsnis. Todėl kilpa ties A įstrižainėje duoda elementą 2, o ne 1.

Pagal kitus matricų sudarymo susitarimus įstrižainėje įrašomas pats kilpų skaičius. Pagal tokį susitarimą paprastoje eilutės sumoje trūksta po vieną kiekvienos kilpos indėlį. Prieš taikydami matricos formulę, perskaitykite taisyklę. Mūsų galinių viršūnių ir incidencijos lentelėse išsaugoma kiekvienos briaunos tapatybė; vien gretimumo skaičiai išsaugo kartotinumą, bet ne pavadinimus e1 ir e2.

Orientuotosios briaunos: įeinantys ir išeinantys lankai

Orientuotoji briauna, dar vadinama lanku, turi pasirinktą pradžią ir pabaigą: A→B prasideda viršūnėje A ir baigiasi viršūnėje B. Priešingos krypties B→A yra kita orientuotoji jungtis. Modelyje gali būti viena iš jų, abi arba nė vienos. Mūsų orientuotuosiuose pavyzdžiuose atskirai pažymėti lygiagretūs lankai ir orientuotosios kilpos leidžiami tik tada, kai jie nurodyti galinių viršūnių sąraše.

Viršūnės v išėjimo laipsnis yra lankų, kurių pradžia yra v, skaičius. Įėjimo laipsnis yra lankų, kurių pabaiga yra v, skaičius. Orientuotoji kilpa ties v prie kiekvieno iš šių skaičių prideda 1. Lygiagretūs lankai skaičiuojami atskirai. Kilpa turi vieną pradžią ir vieną pabaigą, net kai abi yra toje pačioje viršūnėje.

Kai lankai yra A→B, A→C, B→C ir C→B, A išėjimo laipsnis yra 2, o įėjimo laipsnis – 0; B išėjimo laipsnis yra 1, o įėjimo laipsnis – 2; C išėjimo laipsnis yra 1, o įėjimo laipsnis – 2. Išeinančių lankų skaičių suma yra 4, o įeinančių lankų skaičių suma taip pat yra 4; abi sumos lygios lankų skaičiui.

Kiekviename baigtiniame orientuotajame grafe Σ outdegree(v)=|E| ir Σ indegree(v)=|E|. Kiekvienas lankas skaičiuojamas vieną kartą pagal vienintelę jo pradžią ir vieną kartą pagal vienintelę jo pabaigą. Atskirų viršūnių įeinančių ir išeinančių lankų skaičiai nebūtinai yra lygūs: mūsų pavyzdžio A yra kontrpavyzdys. Sudėję abi sumas gauname 2|E|, tačiau kiekviena atskira suma yra |E|.

Orientuotojo grafo gretimumo matricos elementas eilutėje u ir stulpelyje v yra lankų u→v skaičius. Eilučių sumos nurodo išėjimo laipsnius, o stulpelių sumos – įėjimo laipsnius. Ši lentelė nebūtinai yra simetrinė. Kiekviena orientuotoji kilpa prie įstrižainės elemento prideda 1, kitaip nei pagal mūsų susitarimą neorientuotąją kilpą skaičiuoti du kartus. Lanko pradžią ir pabaigą lemia rodyklės kryptis, o ne jo lenktos linijos padėtis.

Numatykite, atskleiskite ir tiksliai atkurkite tinklą

Pasirinkite baigtinį pavyzdį. Prieš atskleidžiant rezultatus matomas paveikslas ir visas galų sąrašas. Numatykite kiekvieną laipsnį arba abu orientuotųjų lankų skaičius; tada parodykite tikslias laipsnių, gretimumo ir incidencijos lenteles. Paryškinta viršūnė A padeda atsekti briaunų galus, o oranžinės brūkšninės briaunos žymi briaunas, incidentiškas A. Skaičiuojant laipsnį, kilpą ties A reikia atsekti du kartus.

Palyginkite du kambarių išdėstymus: visos jungtys ir visi laipsniai turėtų sutapti. Palyginkite susikirtimą su atveju, kai centre pridėta viršūnė: jų lentelės skiriasi, nes skiriasi galų duomenys. Palyginkite vieną orientuotąją kilpą su viena neorientuotąja kilpa: esant tam pačiam briaunų skaičiui, taikomi skirtingi susitarimai dėl matricos įstrižainės elementų, o atitinkami skaičiai abiem atvejais yra teisingi.

Kiekvienas tyrinėjimo priemonės pavyzdys yra visas baigtinis grafas, o ne iškirpta didesnio tinklo dalis. Brėžinys yra scheminis ir neturi ilgio mastelio. Jo lentelėse pateiktos visos nurodytos viršūnės ir briaunos, įskaitant nulius izoliuotosioms viršūnėms. Aukščiau pateikti įrodymai galioja ir kitiems baigtiniams grafams, ne tik šiems pavyzdžiams; vien apžiūrint brėžinius bendros teoremos įrodyti negalima.

Kai vėliau nagrinėsite maršrutus, ciklus ar medžius, nepamirškite šio pirmojo klausimo: kurios jungtys iš tikrųjų yra ir ar jos turi kryptį? Šios temos papildo viršūnių ir briaunų modelį naujais apibrėžimais. Jos nėra būtinos išankstinės žinios šiai pamokai. Grįžkite čia, kai neaiškus galas, susikirtimas ar laipsnio skaičiavimas.

Išnagrinėti pavyzdžiai

Pabandykite patys

1. Ar kambarių tinkle A–B skiriasi nuo B–A? Ar yra A–D?

   Rodyti atsakymą ir paaiškinimą

   A–B ir B–A žymi tą pačią neorientuotąją briauną. A–D nėra.

   Neorientuotosios briaunos galų tvarka nesvarbi; tiksliai išvardytos poros yra A–B, A–C ir B–C.

2. Grafas turi viršūnes A, B, C ir neturi briaunų. Kiek jis turi viršūnių, briaunų ir nelyginio laipsnio viršūnių?

   Rodyti atsakymą ir paaiškinimą

   Trys viršūnės, nulis briaunų ir nulis nelyginio laipsnio viršūnių.

   Kiekviena nurodyta viršūnė išlieka, tačiau visų viršūnių laipsniai yra 0. Nulis yra lyginis skaičius.

3. Kokias briaunas pagal šioje pamokoje taikomą susitarimą gali turėti grafas, kurio V yra tuščia aibė? Patikrinkite viršūnių laipsnių sumą.

   Rodyti atsakymą ir paaiškinimą

   Jis negali turėti jokių briaunų; ir viršūnių laipsnių suma, ir 2|E| yra lygūs 0.

   Briaunai reikia nurodytų galinių viršūnių, o tuščioje viršūnių aibėje jų nėra. Tuščia suma pagal apibrėžimą lygi 0.

4. Viena viršūnė A turi dvi skirtingas neorientuotas kilpas. Raskite |E|, deg(A) ir neorientuoto grafo gretimumo matricos elementą.

   Rodyti atsakymą ir paaiškinimą

   |E|=2, deg(A)=4, o vienintelis gretimumo matricos elementas yra 4.

   Kiekviena kilpa yra viena briauna, kurios abu galai yra viršūnėje A. Mūsų neorientuoto grafo matricos įstrižainėje įrašomas dvigubas kilpų skaičius.

5. Trys atskiri neorientuoti kabeliai jungia A su B. Kam lygus deg(A) ir kiek skirtingų kitų gretimų viršūnių turi A?

   Rodyti atsakymą ir paaiškinimą

   Laipsnis yra 3, o skirtinga kita gretima viršūnė yra viena – B.

   Kiekvienas kabelis prideda atskirą galą, tačiau visi trys jungiasi su ta pačia kita viršūne. Laipsnis ir gretimų viršūnių skaičius sutampa tik esant atitinkamai paprastojo grafo sąlygai.

6. Brėžinyje A–C ir B–D susikerta vieną kartą, o susikirtimo taške nėra papildomos viršūnės. Nurodykite viršūnių ir briaunų skaičių.

   Rodyti atsakymą ir paaiškinimą

   Keturios viršūnės ir dvi briaunos.

   Susikirtimas nesukuria briaunos galo. Pakeitus jį aiškiai pažymėta viršūne E ir keturiomis suskaidytomis briaunomis, būtų aprašytas kitas tinklas.

7. Ar neorientuotojo grafo viršūnių laipsniai gali būti 4,2,1,0? Paaiškinkite remdamiesi bendrąja teorema.

   Rodyti atsakymą ir paaiškinimą

   Ne; laipsnių suma yra 7, o ji negali būti lygi dvigubam sveikajam briaunų skaičiui.

   Kitaip tariant, lygiai viena iš išvardytų viršūnių yra nelyginio laipsnio, o tai prieštarauja teiginiui, kad nelyginio laipsnio viršūnių skaičius yra lyginis.

8. Neorientuotojo grafo viršūnių laipsniai yra 3,3,2,2,0. Jei toks grafas egzistuoja, kiek jis turi briaunų? Ar vien šis skaičiavimas įrodo jo egzistavimą?

   Rodyti atsakymą ir paaiškinimą

   Jis turi turėti penkias briaunas. Vien šis skaičiavimas neįrodo jo egzistavimo.

   Laipsnių suma yra 10, todėl |E|=10/2=5. Rankų paspaudimų formulė yra būtina sąlyga, o ne bendras konstravimo būdas.

9. Kokie įrašai yra neorientuotosios kilpos ties B stulpelyje incidencijos lentelėje, kurios eilutės atitinka viršūnes, o stulpeliai – briaunas?

   Rodyti atsakymą ir paaiškinimą

   Eilutėje B yra įrašas 2, o visose kitose eilutėse – 0.

   Abu šios vienos briaunos galai yra ties B. Stulpelio įrašų suma vis tiek lygi 2.

10. Neorientuotojo multigrafo su viršūnėmis A ir B gretimumo matricos eilutės yra (2,3) ir (3,0). Paaiškinkite, ką jos nusako apie kilpas, lygiagrečias briaunas, viršūnių laipsnius ir briaunų skaičių.

    Rodyti atsakymą ir paaiškinimą

    Viena kilpa ties A, trys A–B briaunos, laipsniai 5 ir 3, iš viso keturios briaunos.

    Įstrižainės elementas 2 reiškia vieną kilpą. Ne įstrižainėje esantis elementas 3 žymi tris identifikuotas jungtis be jų pavadinimų. Laipsnių suma 8 rodo, kad yra keturios briaunos.

11. Vienintelė viršūnė turi vieną orientuotą kilpą. Raskite jos įėjimo laipsnį, išėjimo laipsnį ir orientuotojo grafo gretimumo matricos elementą.

    Rodyti atsakymą ir paaiškinimą

    Visi trys lygūs 1.

    Šis lankas ties viršūne turi vieną galinį ir vieną pradinį tašką. Orientuotojo grafo matricos įstrižainėje kilpos skaičiuojamos po vieną, kitaip nei pagal mūsų neorientuotojo grafo taisyklę, kai kiekviena kilpa skaičiuojama du kartus.

12. Kai yra tik lankai A→B ir A→C, nurodykite visus įeinančių ir išeinančių lankų skaičius. Ar jie turi būti lygūs kiekvienoje viršūnėje?

    Rodyti atsakymą ir paaiškinimą

    A:(0,2), B:(1,0), C:(1,0), poras užrašant (įėjimo laipsnis, išėjimo laipsnis). Viršūnėje jie nebūtinai lygūs.

    Abi bendros sumos lygios 2, tačiau iš A išeina du lankai, o į ją neįeina nė vienas. Teorema teigia bendrų sumų, o ne kiekvienos eilutės atskirų skaičių lygybę.

13. Kodėl vien laipsnių sąrašai neleidžia atskirti {A–B,C–D} nuo {A–C,B–D}?

    Rodyti atsakymą ir paaiškinimą

    Abiejų pažymėtų tinklų laipsniai yra 1,1,1,1, nors jų galinių taškų poros skiriasi.

    Laipsniai išsaugo informaciją, kiek briaunų galų yra ties kiekviena viršūne, bet neišsaugo informacijos, su kuriais kitais galiniais taškais jie sujungti. Išnagrinėkite pačius briaunų duomenis.

14. Pašalinkite kilpą ties A iš keturių briaunų multigrafo e1:A–B,e2:A–B,e3:B–C,e4:A–A. Kas pasikeičia?

    Rodyti atsakymą ir paaiškinimą

    Briaunų skaičius sumažėja nuo 4 iki 3. Viršūnės A laipsnis sumažėja nuo 4 iki 2, o B, C ir D laipsniai lieka 3,1,0.

    Pašalinus kilpą, jos viršūnėje pašalinami du briaunos galai. Laipsnių suma sumažėja nuo 8 iki 6, taigi jos pokytis yra lygiai dvigubai didesnis už vienos briaunos pokytį.

Ką verta įsidėmėti

• Grafas aprašo nurodytas viršūnes ir jungtis; brėžinio susikirtimai ir ilgiai nesuteikia papildomų duomenų apie briaunų galus.
• Skaičiuodami neorientuoto grafo viršūnės laipsnį, skaičiuokite briaunų galus: kiekviena kilpa prideda du, o kiekviena lygiagrečioji briauna skaičiuojama atskirai.
• Neorientuoto grafo viršūnių laipsnių suma lygi dvigubam briaunų skaičiui, todėl nelyginio laipsnio viršūnių skaičius yra lyginis.
• Laipsnių suma yra suderinamumo sąlyga; ji vienareikšmiškai nenusako tinklo ir neįrodo, kad kiekvienas siūlomas laipsnių sąrašas yra realizuojamas.
• Kiekvienas orientuotas lankas vieną kartą įskaičiuojamas į išeinančių lankų sumą ir vieną kartą į įeinančių lankų sumą. Matricos taisyklėse turi būti nurodyta krypties ir kilpų skaičiavimo susitarimas.