Graafiteorian sanasto

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 17. elokuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Tässä on koottu graafiteorian termien määritelmiä . Viittaukset tämän sanakirjan termeihin (tällä sivulla) on kursivoitu .

# A B C D E F F G I K L M N O P R S T U V Y Z _ _ _ _ _ _ _

A

Automorfismi - Kuvaajan isomorfismi itsensä kanssa.
Asyklinen graafi on graafi ilman syklejä .

B

Graafin kanta on graafin kärkijoukon minimaalinen osajoukko, josta mikä tahansa graafin kärkipiste on saavutettavissa.
Ääretön graafi on graafi, jossa on äärettömän monta kärkeä ja/tai kulmia.
Bigraph - katso kaksiosainen kaavio .
Lohko on graafi ilman saranoita .
Lohkosuunnittelu parametreilla (v, k, λ) on v-pisteen täydellisen graafin peittäminen moninkertaisuudella λ k pisteen täydellisillä graafilla.

Kohdassa

Vertexin valenssi - katso kärjen aste .
Vertex , solmu - peruskäsite : piste, jossa reunat ja/tai kaaret voivat lähentyä/poistua. Graafin G kärkijoukkoa merkitään V(G).
Vertex cover on joukko graafin pisteitä siten, että jokainen reuna osuu ainakin yhteen kärkeen tästä joukosta.
Reunan paino on painotetun graafin tietylle reunalle annettu arvo . Yleensä paino on reaaliluku , jolloin se voidaan tulkita reunan " pituudeksi ".
Painotettu graafi on graafi , jonka jokaiselle reunalle on määritetty tietty arvo ( reunapaino ). Katso merkitty kaavio .
Riippuva huippupiste on kärki , jonka aste on yhtä suuri kuin 1 (eli ). $d(v) = 1$

Täysin irrallinen graafi on säännöllinen 0-asteinen graafi, eli graafi ilman reunoja .
Puun korkeus on pisin polku juuresta lehtiin .

G

Hamiltonin graafi on graafi, jolla on Hamiltonin sykli .
Hamiltonin polku on yksinkertainen polku graafissa, joka sisältää kaikki graafin kärjet täsmälleen kerran.
Hamiltonin sykli on yksinkertainen sykli graafissa, joka sisältää kaikki graafin kärjet täsmälleen kerran.
Geometrinen toteutus on kuvio, jonka kärjet vastaavat graafin kärkipisteitä, reunat - graafin reunat ja kuvion reunat yhdistävät graafin kärkipisteitä vastaavat pisteet.
Geometrinen graafi on litteä kuva pisteistä - tason pisteistä ja reunoista - viivoista, jotka yhdistävät joitain pistepareja. Voi esittää mitä tahansa kuvaajaa monin tavoin.
Hypergrafi on joukko kärkijoukkoa ja joukko hypersärmiä (pistejoukon n:nnen euklidisen potenssin osajoukko, eli hyperreunat yhdistävät mielivaltaisen määrän pisteitä).
Homeomorfiset graafit ovat kaavioita, jotka on saatu yhdestä graafista käyttämällä reuna-alajakojen sarjaa.
Pinta on tasograafissa reunojen rajaama alue,ei sisällä graafin kärkipisteitä ja reunoja. Tason ulompi osa muodostaa myös kasvon.
Graafi on peruskäsite. Sisältääja reunajoukon , joka on kärkijoukon suorakulmaisen neliön osajoukko (eli jokainen reuna yhdistää täsmälleen kaksi kärkeä).
Suvun g kuvaaja on graafi, joka voidaan kuvata ilman leikkauskohtia suvun g pinnalla, eikä sitä voida kuvata ilman leikkauskohtia millään suvun g -1 pinnalla. Erityisesti tasokaavioilla on suku 0.

D

Kaksoiskaavio . Graafia A kutsutaan duaaliksi tasograafin B kanssa, jos graafin A kärjet vastaavatgraafin B kasvoja ja graafin A kaksikärkeä on yhdistetty reunalla silloin ja vain, jos graafin B vastaavilla pinnoilla on vähintään yksi yhteinen reuna.
Kaksiosainen graafi (tai bigraf , tai parillinen graafi ) on graafi, jossa kärkijoukko V on jaettu kahteen ei-leikkaavaan osajoukkoonjaja mikä tahansa reuna E osuu kärkeen kohteestaja kärkeen kohteesta(eli se yhdistää kärjen kohteestapisteeseen). Toisin sanoen kaavion oikea väritys suoritetaan kahdella värillä. Joukkojajakutsutaan kaksiosaisen graafin "osiksi". Kaksiosaista graafia kutsutaan "täydelliseksi", jos mitkä tahansa kaksi kärkeäjaovat vierekkäisiä. Jos,niin koko kaksiosainen graafi on merkitty. $G(V,E)$ $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$ $\left|V_{1}\right|=a$ $\left|V_{2}\right|=b$ $K_{{a,b}}$
Kaksinkertaisesti yhdistetty graafi on yhdistetty graafi , jossa ei ole saranoita .
Puu on yhdistetty graafi , joka ei sisällä syklejä .
Kuvaajan halkaisija on pisteiden välinen maksimietäisyys kaikille kärkipareille. Piikkien välinen etäisyys on pienin määrä reunoja polulla , joka yhdistää kaksi kärkeä. $\mathrm {halkaisija} (G)$
Reitin pituus - reitin reunojen määrä (toistoilla). Jos reitti on , M :n pituus on yhtä suuri kuin k (merkitty merkillä ). $M=v_{0},e_{1},v_{1},e_{2},v_{2},...,e_{k},v_{k}$ $\left|M\right|=k$
Polun pituus on polun kaarien lukumäärä (tai sen kaarien pituuksien summa, jos viimeksi mainitut on annettu). Joten polun v 1 , v 2 , …, v n pituus on n-1.
Kaari on suunnattu reuna .
Graafin komplementti on graafi, joka ylittää saman pistejoukon kuin alkuperäinen, mutta kärjet on yhdistetty reunalla silloin ja vain, jos alkuperäisessä graafissa ei ole reunaa.

E

Suuntaamattoman graafin G karhunvatukka on graafin G toisiinsa liittyvien osagraafien perhe,jotka ovat tangentteja keskenään.

W

Tähtikaavio on täydellinen kaksiosainen kaavio. $K_{{1,b}}$

Ja

Eristetty kärkipiste on kärki, jonka aste on 0 (eli siihen ei liity kulmia ) .
Isomorfismi . Kahden graafin sanotaan olevan isomorfinen , jos pisteiden permutaatio on sellainen, että ne ovat samat. Toisin sanoen kahta graafia kutsutaan isomorfiseksi , jos niiden kärkien ja reunojen välillä on yksi-yhteen vastaavuus, joka säilyttää vierekkäisyyden ja insidenssin (graafit eroavat vain kärkien nimissä).
Graafin invariantti on graafin tai sen järjestetyn vektorin numeerinen ominaisuus, joka luonnehtii graafin rakennetta invariantti pisteiden uudelleennumeroinnin suhteen.
Intervalligraafi on graafi, jonka kärjet voidaan osoittaa yksitellen reaaliakselin segmentteihin siten, että kaksi kärkeä osuu samaan reunaan silloin ja vain, jos näitä pisteitä vastaavat segmentit leikkaavat toisiaan.
Tapahtuma on käsite, jota käytetään vain suhteessa reunaan tai kaareen ja kärkeen: jos ovat kärjet ja a on niitä yhdistävä reuna, niin kärki ja reuna ovat sattuvia, ja kärki ja reuna ovat myös sattuvia. Kaksi kärkeä (tai kaksi reunaa) eivät voi olla sattuvia. Lähimpien kärkien (reunojen) merkitsemiseen käytetään vierekkäisyyden käsitettä . $v_{1}, v_{2}$ $e=(v_{1},v_{2})$ $v_{1}$ $e$ $v_{2}$ $e$

K

Solu on säännöllinen kuvaaja, joka esittää pienimmän ympärysmitan tietylle kärkiasteen.
Klikki on graafin kärkipisteiden osajoukko, jotka ovat täysin yhteydessä toisiinsa, eli aligraafi, joka on täydellinen graafi .
- Klikkien luku on suurimman klikin kärkien lukumäärä (G) . Muut nimet ovat tiheys, tiheys.
- Maksimiklikki on klikki, jolla on suurin mahdollinen määrä pisteitä graafin klikkien joukossa.
Pyörä (merkitty W n ) on graafi, jossa on n kärkeä (n ≥ 4), joka muodostetaan yhdistämällä yksi kärki ( n -1) -syklin kaikkiin pisteisiin.
Värinä on vain suunnattu graafi.
Äärillinen graafi on graafi, joka sisältää äärellisen määrän pisteitä ja kulmia.
Graafeiden rakentava luettelointi - täydellisen luettelon saaminen tietyn luokan kaavioista.
Graafin yhdistetty komponentti on graafin kärkien osajoukko , jonka kahdelle kärjelle on polku yhdestä toiseen, eikä polkua tämän osajoukon kärjestä ole kärkeen, joka ei ole tästä osajoukosta. .
Graafin vahvasti yhdistetty komponentti , kerros on suunnatun graafin pisteiden maksimijoukkositen, että mille tahansa kahdelle tästä joukosta olevalle pisteelle on polku sekä ensimmäisestä toiseen että toisesta ensimmäiseen.
Ääriviiva on suljettu polku digraafissa .
Puun juuri on puun valittu solmu ; digraafissa piste, jonka sisääntuloaste on nolla.
Yhteissykli on minimaalinen leikkaus , minimaalinen joukko reunoja, joiden poistaminen tekee graafista irti.
Useat reunat ovat useita reunoja , jotka osuvat samaan kärkipariin. Löytyy monigraafista .
Kuutiograafi on 3-asteen säännöllinen graafi, eli graafi, jossa jokaisessa kärjessä on täsmälleen kolme reunaa.
k-osainen graafi on graafi G, jonka kromaattinen luku c(G)=k
K-kytketty graafi on yhdistetty graafi , jossa ei ole pistejoukkoaonvähemmänniihin osuvien kärkien ja reunojen poistaminen katkaisee graafin kytkennän. Erityisesti yhdistetty graafi on 1-kytketty ja kaksinkertaisesti yhdistetty graafi on 2-kytketty. $V'$ $k-1$ $V'$

L

Laman-graafi , jossa on n pistettä, on sellainen graafi G , että ensinnäkin jokaiselle k :lle millä tahansa G :n aligraafilla, joka sisältää k pistettä, on enintään 2 k − 3 reunaa ja toiseksi graafilla G on täsmälleen 2 n −3 reunaa.

Metsä on suuntaamaton graafi ilman syklejä. Puut ovat metsän yhteyskomponentteja .
Puun lehti on puun kärki , jossa on yksi reuna tai sisääntuleva kaari .
Huippupisteen paikallinen aste on siihen osuvien reunojen lukumäärä. Silmukka antaa arvon "2" kärjen asteeseen.

M

Maxi-koodi on vaikeasti laskettava täydellinen graafiinvariantti , joka saadaan kirjoittamalla vierekkäisyysmatriisin binääriarvot riville, minkä jälkeen tuloksena oleva binääriluku muunnetaan desimaalimuotoon. Maxi-koodi vastaa sellaista rivien ja sarakkeiden järjestystä, jossa tuloksena oleva arvo on suurin mahdollinen. $\mu _{max}$
Suurin vastaavuus kaaviossa. Täsmäystä kutsutaan maksimaaliseksi, jos jollakin muulla vastaavuudella on vähemmän reunoja.
Graafin reitti on vuorotteleva kärkien ja reunojen sarja, jossa mitkä tahansa kaksi vierekkäistä elementtiä kohtaavat . Jos , niin reitti on suljettu , muuten se on auki . $v_{0},e_{1},v_{1},e_{2},v_{2},...,e_{k},v_{k}$ $v_{0}=v_{k}$
Digraafin saavutettavuusmatriisi on matriisi, joka sisältää tietoa digraafin kärkien välisten polkujen olemassaolosta.
Graafin insidenssimatriisi on matriisi, jonka elementtiarvoille on ominaista graafin vastaavien kärkien (pystysuoraan) ja sen reunojen (vaakasuunnassa) esiintyvyys. Suuntaamattoman graafin kohdalla elementti saa arvon 1 , jos sen vastaava kärkipiste ja reuna ovat sattuvia. Suunnatussa graafissa elementti saa arvon 1 , jos tuleva kärkipiste on reunan alku, arvon -1 , jos tuleva kärki on reunan loppu; muissa tapauksissa (mukaan lukien silmukat ) elementin arvoksi annetaan 0 .
Graafin vierekkäisyysmatriisi on matriisi, jonka elementtiarvoille on ominaista graafin kärkien viereisyys. Tässä tapauksessa matriisielementin arvolle annetaan määrä reunoja, jotka yhdistävät vastaavat kärjet (eli jotka ovat sattumanvaraisia molemmille pisteille).
Minikoodi on vaikeasti laskettava koko graafin invariantti , joka saadaan kirjoittamalla vierekkäisyysmatriisin binääriarvot riviksi ja muuttamalla sitten saatu binääriluku desimaalimuotoon. Minikoodi vastaa sellaista rivien ja sarakkeiden järjestystä, jossa tuloksena oleva arvo on pienin mahdollinen. $\mu _{min}$
Graafin vähimmäiskehys (tai vähimmäispainokehys , minimi virittävä puu ) on asyklinen (ilman syklejä) reunojen joukko yhdistetyssä, painotetussa ja suuntaamattomassa graafissa, joka yhdistää tämän graafin kaikki kärjet, kun taas kaikkien graafin painojen summa. sen reunat ovat minimaaliset.
Huippupisteen v viereisyysjoukko on kärjen v vieressä olevien kärkien joukko . Nimetty . $\Gamma ^{+}(v)$
Graafi-molli on graafi, joka voidaan saada alkuperäisestä graafista poistamalla ja supistamalla kaaria.
Silta on reuna , jonka poistaminen lisäägraafin yhdistettyjen komponenttien määrää.
Multigrafi on graafi, jossa voi olla pari pisteitä, joita yhdistää useampi kuin yksi reuna (suuntaamaton) tai useampi kuin kaksi vastakkaisen suunnan kaaria.

H

Suunnattu graafi on suunnattu graafi , jossa kaksi kärkeä on yhdistetty enintään yhdellä kaarella.
- Suunnattu asyklinen graafi on suunnattu graafi ilman ääriviivoja .
Itsenäinen pistejoukko (tunnetaan myös nimellä sisäisesti stabiili joukko ) on graafin G kärkijoukko, jossa mitkään kaksi kärkeä eivät ole vierekkäin (mitään pisteparia ei ole yhdistetty reunalla).
- Itsenäistä joukkoa kutsutaan maksimaaliksi , kun ei ole toista riippumatonta joukkoa, johon se kuuluisi. Suurimman itsenäisen joukon komplementtia kutsutaan graafin minimipisteen peitteeksi .
- Suurin itsenäinen joukko on suurin itsenäinen joukko.
Riippumattomat kärjet ovat graafin pareittain ei-vierekkäisiä pisteitä. [yksi]
Erottamaton graafi on yhdistetty, ei-tyhjä graafi ilman artikulaatiopisteitä. [2] .
Normoitu graafi on suunnattu graafi ilman jaksoja .

Nollagraafi ( tyhjä graafi ) on graafi ilman pisteitä .

Voi

Ympärysmitta on kaavion pienimmän syklin pituus.
Graafeiden liitto (merkitty graafitja) on graafijonka kärkijoukko on, ja reunajoukko on. $G_{1}=(X_{1},U_{1})$ $G_{2}=(X_{2},U_{2})$ $G_{1}\kuppi G_{2}$ $X_{1}\kuppi X_{2}$ $U=U_{1}\kuppi U_{2}$
K -asteen naapurusto on joukko pisteitä etäisyydellä k annetusta kärjestä v ; joskus tulkitaan laajasti joukoksi pisteitä, jotka erotetaan v :stä enintään k etäisyydellä .
Ympäristö on joukko pisteitä, jotka ovat annetun pisteen vieressä.
Digraafi , suunnattu graafi G = (V,E) on joukkopari, jossa V on joukko pisteitä (solmuja), E on joukko kaaria (suunnattuja reunoja). Kaari on järjestetty pistepari (v, w), jossa kärkeä v kutsutaan kaaren alusta ja w on kaaren loppu. Voidaan sanoa, että kaari v → w johtaa kärjestä v kärkeen w, kun taas kärki w on kärjen v vieressä.
(Ohjaamattoman) yhdistetyn graafin virittävä puu ( runko ) on mikä tahansa osagraafi , joka on puu . $G=(V,E)$ $S=(V,T)$
Virittävä osagraafi on osagraafi, joka sisältää kaikki kärjet.

P

Vastaavuus on joukko pareittain ei-vierekkäisiä reunoja.
Silmukka on reuna, jonka alku ja loppu ovat samassa kärjessä.
Graafeiden (merkitty graafitja) leikkauspiste on graafijonka kärkijoukko on, ja reunajoukko on. $G_{1}=(X_{1},U_{1})$ $G_{2}=(X_{2},U_{2})$ $G_{1}\cap G_{2}$ $X_{1}\cap X_{2}$ $U=U_{1}\cap U_{2}$
Graafinen numerointi - ei-isomorfisten graafien lukumäärän laskeminen tietyssä luokassa (annetuilla ominaisuuksilla).
Kehäpiste on kärki, jonka epäkeskisyys on yhtä suuri kuin kuvaajan halkaisija.
Tasograafi on graafi, joka voidaan piirtää ( pinota ) tasolle risteämättä reunoja. Se on isomorfinen tasograafin kanssa , eli se on graafi, jossa on leikkauspisteet, mutta sallien sen tasomaisen asettelun, joten se voi poiketa tasograafista tasossa olevalla kuvalla. Siten tasokuvaajan ja tasograafin välillä voi olla ero, kun se esitetään tasossa.
Tasograafi on geometrinen graafi , jossa kahdella reunalla ei ole yhteisiä pisteitä, lukuun ottamatta molempien kohtaavaa kärkeä (ne eivät leikkaa). Se on pinottu kaavio tasossa.
Alkuperäisen graafin aligraafi on graafi, joka sisältää tietyn graafin kärkien osajoukon ja tietyn niihin kohdistuvien reunojen osajoukon. (vrt. sugraph .) Alkuperäistä kuvaajaa kutsutaan osagraafin suhteen supergraafiksi
Täydellinen graafi on graafi, jossa jokaiselle kärkiparilleon reuna, sattumaja sattuma(jokainen kärki on yhdistetty reunalla mihin tahansa toiseen kärkeen). $v_{1}, v_{2}$ $v_{1}$ $v_{2}$
Täydellinen graafiinvariantti on graafin tai sen järjestetyn vektorin numeerinen ominaisuus, jonka arvot ovat välttämättömiä ja riittäviä graafin isomorfismin määrittämiseksi
Täydellinen kaksiosainen graafi on kaksiosainen graafi , jossa yhden osajoukon kukin kärki on yhdistetty reunalla toisen osajoukon kuhunkin kärkeen
Huippupisteen digraafin in -aste on kärkeen saapuvien kaarien lukumäärä. Merkitään , , tai . $v$ $d^{+}(v)$ $\mathrm {deg} ^{+}(v)$ $\mathrm {indeg} (v)$ $d_{t}(v)$
Huippupisteen digraafin ulkoaste on kärjestä lähtevien kaarien lukumäärä. Merkitään , , tai . $v$ $d^{-}(v)$ $\mathrm {deg} ^{-}(v)$ $\mathrm {outdeg} (v)$ $d_{o}(v)$
Merkitty graafi on graafi, jonka huipuille tai kaarille on liitetty jonkinlainen tunniste, esimerkiksi luonnolliset numerot tai jonkin aakkoston symbolit.
Luotu osagraafi on alkuperäisen graafin reunajoukon luoma osagraafi. Se ei välttämättä sisällä kaikkia graafin kärkipisteitä, mutta nämä kärjet on yhdistetty samoilla reunoilla kuin graafissa.
Graafin järjestys on graafin kärkien lukumäärä. [3]
Oikea graafin väritys on sellainen väritys , että jokainen väriluokka on itsenäinen joukko. Toisin sanoen oikealla värityksellä kahdella vierekkäisellä kärjellä on oltava eri värit.
Graafeiden tulo - annetuille graafeille tulo on graafi , jonka kärjet ovat alkuperäisten graafien kärkijoukkojen karteesinen tulo. $G_{1}=(V_{1},E_{1})$ $G_{2}=(V_{2},E_{2})$ $G=(V,E)$ $V(G)=V_{1}\kertaa V_{2}$
Yksinkertainen polku on polku , jonka kaikki kärjet ovat erillisiä.
Yksinkertainen graafi on graafi , jossa ei ole useita reunoja tai silmukoita .
Yksinkertainen polku on polku , jonka kaikki kärjet ovat pareittain erillisiä [4] . Toisin sanoen yksinkertainen polku ei kulje saman kärjen läpi kahdesti.
- Yksinkertainen sykli on sykli , joka ei kulje saman kärjen läpi kahdesti.
Pseudografi on graafi, joka voi sisältää silmukoita ja/tai useita reunoja.

Tyhjä graafi ( nollagraafi ) on graafi ilman reunoja .
Polku on sarja reunoja (suuntaamattomassa graafissa) ja/tai kaaria (suunnatussa graafissa), jolloin yhden kaaren (reuna) loppu on toisen kaaren (reuna) alku. Tai kärkipisteiden ja kaarien (reunojen) sarja, jossa jokainen elementti osuu edelliseen ja seuraavaan [4] . Voidaan ajatella reitin erikoistapauksena .
Digraafin polku on sarja pisteitä v 1 , v 2 , …, v n , joille on olemassa kaaria v 1 → v 2 , v 2 → v 3 , …, v n-1 → v n . Tämän polun sanotaan alkavan kärjestä v 1 , kulkevan kärkien v 2 , v 3 , …, v n-1 kautta ja päättyvän kärkeen v n .

R

Kuvaajan säde on yhdistetyn graafin kärkien epäkeskisuuksien minimi ; huippua, jossa tämä minimi saavutetaan, kutsutaan keskihuipukseksi.
Graafin jakaminen on alkuperäisen graafin esitys pisteiden osajoukkoina tiettyjen sääntöjen mukaisesti.
Jaettu kärkipiste on sama kuin sarana ja nivelpiste .
Graafin avautuminen on funktio, joka on määritelty suunnatun graafin huipuissa.
Merkitty graafi on graafi, jolle on annettu joukko tunnisteita S, kärkipisteiden merkintäfunktio f : A → S ja kaarimerkintäfunktio g : R → S. Graafisesti nämä funktiot esitetään pisteissä ja kaarissa olevilla nimiöillä. Tarrajoukko voidaan jakaa kahteen ei-päällekkäiseen kärkimerkkien ja kaaritarrojen osajoukkoon.
Leikkaus on joukko reunoja , joiden poistaminen tekee graafista irti .
Kehysgraafi on graafi, joka voidaan piirtää tasoon siten, että mikä tahansa rajattu pinta on nelikulmio ja mikä tahansa kärki, jolla on enintään kolme naapuria, osuu rajoittamattomaan pintaan. [5]
Graafin väritys on kärkien jakamista joukoiksi (kutsutaan väreiksi). Jos lisäksi ei ole kahta vierekkäistä pistettä, jotka kuuluvat samaan joukkoon (eli kaksi vierekkäistä kärkeä ovat aina erivärisiä), niin tällaista väritystä kutsutaan säännölliseksi.
Piikkien välinen etäisyys on lyhimmän ketjun pituus (polun digraafissa), joka yhdistää annetut kärjet. Jos tällaista ketjua (polkua) ei ole olemassa, etäisyyden oletetaan olevan ääretön.
Reunapeite on joukko graafin reunoja siten, että jokainen kärki kohtaa ainakin yhden tämän joukon reunan.
Suuntaamattoman graafin viivakaavio on graafi, joka edustaa graafin reunojen lähialuetta.
Edge on peruskäsite. Reuna yhdistää graafin kaksi kärkeä .
Säännöllinen graafi on graafi, jonka kaikkien kärkien asteet ovat yhtä suuret. Säännöllisyyden aste onkaavion invariantti ja sitä merkitään . Määrittelemätön epäsäännöllisille kaavioille. Säännölliset kaaviot ovat erityinen haaste monille algoritmeille. $r(G)$ $r(G)$
- Säännöllinen 0-asteen graafi ( täysin irrotettu graafi , tyhjä graafi , nollagraafi ) on graafi ilman reunoja .

C

Itsekaksoisgraafi on graafi, joka on isomorfinen sen kaksoisgraafin kanssa .
Hyperkapea (tähdenmuotoinen) puu on puu, jonka yksi kärkiaste on suurempi kuin 2.
Liitettävyys . Graafin kaksi kärkeä ovat yhteydessä toisiinsa , jos ne yhdistää (yksinkertainen) polku .
Yhdistetty graafi on graafi, jonka kaikki kärjet ovat yhteydessä toisiinsa.
Graafin osa on joukko reunoja, joiden poistaminen jakaa graafin kahteen erilliseen osagraafiin, joista yksi voi erityisesti olla triviaaligraafi.
Verkko on periaatteessa sama kuin graafi , vaikka verkkoja kutsutaan yleensä graafiksi, joiden kärjet on merkitty tietyllä tavalla.
- Suunnattu verkko on suunnattu graafi, joka ei sisällä ääriviivoja.
Vahva liitettävyys . Suunnatun graafin kaksi kärkeä ovat vahvasti yhteydessä toisiinsa , jos ensimmäisestä toiseen on polku ja toisesta ensimmäiseen.
- Vahvasti yhdistetty digraafi on digraafi , jonka kaikki kärjet ovat vahvasti yhteydessä toisiinsa.
Vierekkäisyys - käsite, jota käytetään suhteessa vain kahteen reunaan tai vain kahteen kärkeen : Kahta yhteen kärkeen kohdistuvaa reunaa kutsutaan vierekkäisiksi ; kahta samaan reunaan osuvaa kärkeä kutsutaan myös vierekkäisiksi . (vrt. Tapahtuma .)
Sekagraafi on graafi, joka sisältää sekä suunnatut että suuntaamattomat reunat .
Täydellinen vastaavuus on sovitus, joka sisältää kaikki graafin kärjet.
Kahden graafin ja , joilla ei ole yhteisiä pisteitä, yhteyttä kutsutaan graafiksi . [6] $G_{1}=(V_{1},E_{1})$ $G_{2}=(V_{2},E_{2})$ $G_{1}+G_{2}=(V_{1}\kuppi V_{2},E_{1}\kuppi E_{2}\kuppi V_{1}\kertaa V_{2}\kuppi V_{2} \times V_{1})$

Määritelmästä voidaan nähdä, että graafien yhteydellä on kommutatiivisuuden ja assosiatiivisuuden ominaisuuksia

Graafin spektri on joukko vierekkäisyysmatriisin kaikki ominaisarvot, ottaen huomioon useat reunat.
Huippupisteen aste on niiden graafin G reunojen lukumäärä,jotkakohtaavat kärjen x . Nimetty. Graafin G kärjen minimiaste on merkitty. ja maksimi on. $d(x)$ $\delta (G)$ $\Delta (G)$
Graafin reunan supistuminen - reunan päiden korvaaminen yhdellä kärjellä, näiden päiden naapureista tulee uuden kärjen naapureita. Graafi on supistuva ,jos toinen voidaan saada ensimmäisestä reunasupistumien sarjalla. $G_{1}$ $G_{2}$
Alkuperäisen graafin osagraafi ( osittaisgraafi ) on graafi, joka sisältää kaikki alkuperäisen graafin kärjet ja osan sen reunoista . (vrt. alakaavio .)
Supergraafi - mikä tahansa kaavio, joka sisältää alkuperäisen kaavion (eli jonka alkuperäinen kaavio on alikuvaaja )

T

Theta-graafi on graafi, joka koostuu kolmen polun liitosta, joilla ei ole yhteisiä pisteitä sisällä ja joilla on samat päätepisteet [7]
Euklidisen tason pistejoukon theta-graafi on konstruoitu kutakin kärkeä ympäröiväksi kartiojärjestelmäksi, jossa kullekin kartiolle on lisätty reuna joukon pisteeseen, jonka projektio kartion keskiakselille on minimaalinen.

Identiteettigraafi on graafi, jolle on mahdollista vain yksi automorfismi - . Kuvannollisesti puhuen identiteettikaavio on "absoluuttisesti epäsymmetrinen" graafi.
Nivelpiste on sama kuin sarana ja jakopiste .
Pintakolmio - kaavion asettaminen pinnalle , jakamalla se kolmion muotoisiksi alueiksi; topologisen kolmion erikoistapaus .
Triviaaligraafi on graafi, jolla on enintään yksi kärki .
Turnaus on suunnattu graafi , jossa jokainen kärkipari on yhdistetty yhdellä reunalla.

Wu

Solmu on sama kuin Vertex .
Pinoaminen tai graafin upottaminen : graafi pinotaan jollekin pinnalle, jos se voidaan piirtää tälle pinnalle siten, että graafin reunat eivät leikkaa toisiaan. (Katso tasokaavio , tasokuvaaja .)
Suoja on tietyntyyppinen funktio suuntaamattoman graafin kärkijoukoissa. Jos peitto on olemassa, pakolainen voi käyttää sitä voittaakseen jahdata-väistöpelin kaaviossa käyttämällä tätä toimintoa pelin jokaisessa vaiheessa määrittääkseen turvalliset pistejoukot, joihin mennä.
Järjestetty graafi on graafi, jossa kustakin kärjestä lähtevät reunat on numeroitu yksiselitteisesti alkaen 1:stä. Reunojen katsotaan olevan nousevassa numerojärjestyksessä. Graafisessa esityksessä reunojen katsotaan usein olevan jonkin vakioläpikulkujärjestyksen mukaisessa järjestyksessä (esimerkiksi vastapäivään ).

F

Graafin n-tekijä on säännöllinen ulottuva asteen osagraafi . $n$
graafin n -kerroin - graafin jakaminen itsenäisiksi n-tekijöiksi .

X

Graafin kromaattinen lukumäärä on värien vähimmäismäärä, joka tarvitaangraafin kärkien värjäämiseen siten, että kaikki reunalla yhdistetyt kärjet värjätään eri väreillä.
Graafin ominaispolynomi on sen viereisyysmatriisin karakteristinen polynomi .

C

Kuvaajan keskipiste on joukko pisteitä, joille yhtälö on totta:, missä on kärjen epäkeskisyys ja graafin säde. $W=\vasen\{u_{1},u_{2},...,u_{n}\oikea\}$ $\forall i=1,...,n:\varepsilon (u_{i})=r(G)$ $\varepsilon$ $r$
Graafissa oleva ketju on reitti , jonka kaikki reunat ovat erilliset. Jos kaikki kärjet (ja siten myös reunat) ovat erilaisia, niin tällaista ketjua kutsutaan yksinkertaiseksi ( alkeis ). Ketjussa pisteitä ja kutsutaan ketjun päiksi. Ketju, jonka päät ovat u ja v , yhdistää kärjet u ja v . Huippupisteitä u ja v yhdistävä ketju on merkitty . Digrafien kohdalla ketjua kutsutaan orchainiksi. $v_{0},e_{1},...,e_{k},v_{k}$ $v_{0}$ $v_{k}$ $\left\langle u,v\right\rangle$ Joissakin lähteissä yksinkertainen ketju on ketju, jonka reunat ovat selkeät, mikä on heikompi tila.
Kierto on suljettu piiri . Digrafien kohdalla sykliä kutsutaan ääriviivaksi .
- Digrafin sykli ( yksinkertainen sykli ) on yksinkertainen polku , jonka pituus on vähintään 1 ja joka alkaa ja päättyy samaan kärkeen.
- Hamiltonin sykli on sama kuin Hamiltonin sykli .
Graafin syklomaattinen luku on reunojen vähimmäismäärä, joka on poistettava, jotta graafista tulee asyklinen . Yhdistetylle graafille on olemassa relaatio:missä on syklomaattinen luku, ongraafin yhdistettyjen komponenttien lukumäärä, on reunojen lukumäärä ja on pisteiden lukumäärä . $p_{1}(G)=p_{0}(G)+|E(G)|-|V(G)|,$ $p_{1}(G)$ $p_{0}$ $|E(G)|$ $|V(G)|$

H

Osittaisgraafi on sama kuin sugraafi .
Parillinen graafi on sama kuin kaksiosainen graafi .
Vertex cover number — graafin pienimmän kärjen peitteen koko.
Riippumattomuusluku on graafin suurimman riippumattoman kärkijoukon koko.
Vastaava luku on kaavion suurimman vastaavuuden koko.
Reunapeitenumero — kaavion pienimmän reunapeitteen koko.

W

Sarana on graafin kärkipiste , jonka seurauksena yhdessä kaikkiensiihen kohdistuvien reunojen kanssa graafin yhteenliitettyjen komponenttien määräkasvaa sen poistamisen seurauksena.
Hammaspyörä (merkitty ) on kaavio, joka saadaan pyörästä asettamalla lisäpisteitä kunkin kehän vierekkäisen kärkiparin väliin . Hammaspyörät kuuluvat kehyskaavioiden perheeseen ja niillä on tärkeä rooli kehyskaavioiden kiellettyjen aligraafien kuvauksessa [8] $G_{n}$

E

Euler-graafi on graafi, jossa on sykli , joka sisältää kaikki graafin reunat kerran (pisteet voidaan toistaa).
Euler-ketju (tai Euler-sykli ) - ketju ( sykli ), joka sisältää kaikki graafin reunat (pisteet voidaan toistaa).
Huippupisteen epäkeskisyys on suurin kaikista pienimmistä etäisyyksistä muista pisteistä tiettyyn kärkeen.
Alkeispolku on polku , jonka kärjet ensimmäistä ja viimeistä mahdollisesti lukuun ottamatta ovat erilaiset. Toisin sanoen yksinkertainen polku ei kulje saman kärjen läpi kahdesti, vaan se voi alkaa ja päättyä samaan kärkeen, jolloin sitä kutsutaan sykliksi (alkeiskierto).
Seuraavaa menettelyä kutsutaan alkeissupistumiseksi : otamme reunan (yhdessä siihen kohdistuvien kärkien kanssa , esim. u ja v) ja "supistamme" sen, eli poistamme reunan ja tunnistamme kärjet u ja v. Tällä tavalla saatu kärki kohdistuu niihin reunoihin (muihin kuin), joihin u tai v alun perin kohdistuivat.

Linkit

↑ Distel R. Graafiteoria Per. englannista. - Novosibirsk: Matematiikan instituutin kustantamo, 2002. - s. 17.
↑ Harari F. Graafiteoria. - M.: Mir, 1972. - S. 41.
↑ Distel R. Graafiteoria Per. englannista. - Novosibirsk: Matematiikan instituutin kustantamo, 2002. - S. 16.
↑ 1 2 Kuznetsov O. P., Adelson-Velsky G. M. / Diskreetti matematiikka insinöörille. / M .: Energia, 1980-344 s., ill. Sivu 120-122
↑ A. V. Karzanov. Äärillisten mittareiden laajennukset ja laitteiden sijoitusongelma // Proceedings of the ISA RAS. - 2007. - T. 29 . - S. 225-244 (241) .
↑ M. B. Abrosimov. Minimaalisella kärjellä 1-erikoismuotoisten graafien yhteyksien laajennukset. // Applied Graph Theory - 2011. - Numero. 4 .
↑ JA Bondy. . - Springer, 1972. - T. 303. - S. 43–54. — (Matematiikan luentomuistiinpanot). - doi : 10.1007/BFb0067356 .
↑ H.-J. Bandelt, V. Chepoi, D. Eppstein. Äärillisten ja äärettömien neliögraafien kombinatoriikka ja geometria // SIAM Journal on Discrete Mathematics . - 2010. - T. 24 , no. 4 . - S. 1399-1440 . - doi : 10.1137/090760301 . - arXiv : 0905.4537 . .

Kirjallisuus

Distel R. Graafiteoria Per. englannista. - Novosibirsk: Matematiikan instituutin kustantamo, 2002. - 336 s.
Harari F. Graafiteoria. — M .: URSS , 2003. — 300 s. — ISBN 5-354-00301-6 .