Graafiteorian sanasto - Glossary of graph theory

Tämä on graafiteorian sanasto . Graafiteoria on graafien , solmujen tai pisteiden järjestelmien tutkimus , jotka on yhdistetty pareittain viivoilla tai reunoilla .

Symbolit

Hakasulkeet []: $G [S]$ on indusoitu aligraafi kuvaajan $G$ varten kärki osajoukon $S$ .
Pääsymboli ': Pilkkusymbolilla käytetään usein muuttamaan merkintätapa kuvaajan invariants siten, että se koskee viivakaavio sijaan tietyn kuvaajan. Esimerkiksi $α (G)$ on kaavion riippumattomuusluku; $α' (G)$ on kuvaajan vastaava numero, joka vastaa sen viivakaavion riippumattomuuslukua. Samoin $χ (G)$ on kuvaajan kromaattinen luku; $χ' (G)$ on kuvaajan kromaattinen indeksi, joka vastaa sen viivakaavion kromaattista lukua.

A

imeytyvä: Suunnatun kuvaajan absorboiva joukko on joukko pisteitä siten, että missä tahansa kärjessä on reuna kohti pistettä . ${\ displaystyle A}$ ${\ displaystyle G}$ ${\ displaystyle v \ in G \ setminus A}$ ${\ displaystyle v}$ ${\ displaystyle A}$
akromaattinen: Akromaattinen määrä graafin on maksimimäärä värien täydellisen väritys.
asyklinen: 1. Kaavio on asyklinen, jos sillä ei ole jaksoja. Ohjaamaton asyklinen kuvaaja on sama asia kuin metsä . Suunnattuja asyklisiä kaavioita kutsutaan harvemmin asyklisiksi suunnatuiksi kuvaajaiksi.; 2. Ohjaamattoman käyrän asyklinen väritys on oikea väritys, jossa joka toinen väriluokka aiheuttaa metsän.
vierekkäismatriisi: Vierusmatriisi kuvaajan on matriisi, jonka rivit ja sarakkeet ovat molemmat indeksoidaan graafin solmut, joilla on yksi solu rivin $i$ ja sarakkeen $j$ kun pisteiden $i$ ja $j$ ovat vierekkäin, ja muuten nolla.
vierekkäin: 1. Suhde kahden kärjen välillä, jotka ovat molemmat saman reunan päätepisteitä.; 2. Suhde kahden erillisen reunan välillä, joilla on loppupiste.
α: Varten kuvaaja, $G$ , $α (G)$ (käyttäen kreikkalainen kirjain alfa) on sen riippumattomuus (katso riippumattomia ), ja $α'(G)$ on sen vastaava määrä (katso matching ).
vuorotellen: Kaaviossa, jossa on täsmäytys, vuorotteleva polku on polku, jonka reunat vuorottelevat sovitettujen ja vastaamattomien reunojen välillä. Vaihteleva sykli on vastaavasti sykli, jonka reunat vuorottelevat sovitettujen ja vastaamattomien reunojen välillä. Lisäyspolku on vuorotteleva polku, joka alkaa ja päättyy tyydyttymättömiin pisteisiin. Suurempi vastaavuus löytyy sovituksen ja lisäyspolun symmetrisestä erosta ; täsmäytys on suurin silloin ja vain, jos sillä ei ole lisäyspolkua.
ketjunvastainen: On suunnattu asyklinen kaavio , osajoukko $S$ solmuja, jotka ovat pareittain vailla, eli mitään vuonna $S$ , ei ole suunnattu polku $x$ ja $y$ tai $y$ ja $x$ . Innoittamana käsitteen antiketju vuonna osittain järjestetty joukko . ${\ displaystyle x \ leq y}$
reunan vastainen: Synonyymi ei-reuna , pari vierekkäisiä kärkipisteitä.
anti-kolmio: Kolmen kärjen riippumaton joukko, kolmion täydennys.
kärki: 1. Huippukäyrä on kuvaaja, jossa yksi kärki voidaan poistaa jättäen tasomainen alikuvaaja. Poistettua kärkeä kutsutaan huipuksi. $K$ -apex kaavio on graafinen esitys, joka voidaan tehdä tasomainen poistamalla $k$ pisteiden.; 2. Synonyymi universaalille kärkipisteelle , joka on kaikkien muiden kärkien vieressä.
arboresenssi: Synonyymi juurtuneelle ja suunnatulle puulle; katso puu .
kaari: Katso reuna .
nuoli: Järjestetty pari on pisteiden , kuten reuna on suunnattu verkko . Nuoli $(x, y)$ on häntä $x$ , joka on pää $y$ , ja suunta $välillä x ja y$ ; $y$ sanotaan olevan suora seuraaja on $X$ ja $X$ suora edeltäjä on $y$ . Nuoli $(y, x)$ on nuolen $($ $x$ $,$ $y$ $)$ käänteinen nuoli .
artikulaatiopiste: Kärki on liitetty kaavio joiden poistaminen voisi irrota kuvaaja.
-harmaa: $K$ aarisen puu on juurtunut puu, jossa jokainen sisäinen kärki on enintään $k$ lasta. Yksivuotinen puu on vain polku. 2-kaarista puuta kutsutaan myös binääripuuksi , vaikka tämä termi viittaa paremmin 2-kaarisiin puihin, joissa kunkin solmun lapset erotetaan vasemman- tai oikeanpuoleisiksi lapsiksi (korkeintaan yksi kustakin tyypistä). $K$ aarisen puu sanotaan olevan täydellinen, jos jokainen sisäinen kärki on täsmälleen $k$ lasta.
lisääminen: Erityinen vuorotteleva polku; katso vuorotellen .
automorfismi: Kaavio automorphism on symmetria kaavio, isomorfismi kaaviosta itseensä.

B

laukku: Yksi puun hajoamispisteistä .
tasapainoinen: Kahden- tai moniosainen kuvaaja on tasapainossa, jos sen kärkiosion kumpikin osajoukko on kooltaan toistensa sisällä.
kaistanleveys: Kaistanleveys graafin $G$ on pienin, kaikkien järjestykset kärkien $G$ , ja pisimmän reunan (vaiheiden lukumäärä on tilaus välillä sen kahden päätepisteen). Se on myös yksi pienempi kuin maksimiklikin koko, kun $G$ : n oikea aikaväli on valittu minimoimaan klikin koko.
polkupyörä: Synonyymi täydelliselle kahden osapuolen kuvaajalle tai täydelliselle kahden osapuolen kuvaajalle ; katso täydellinen .
kaksoiskytketty: Yleensä synonyymi $2$ -vertex-kytketty , mutta joskus sisältää K _2, vaikka se ei ole 2-kytketty. Katso kytketty ; ja biconnected komponentit , katso komponentti .
sitova numero: Pienin mahdollinen suhde pisteiden oikean osajoukon naapureiden lukumäärästä osajoukon kokoon.
kaksipuolinen: Kaksijakoinen verkko on kuvaaja, jonka kärjet voidaan jakaa kahteen erilliseen joukkoon siten, että pisteiden yhdet eivät ole yhteydessä toisiinsa, mutta ne voidaan liittää pisteiden toiseen sarjaan. Toisin sanoen kaksipuolinen kuvaaja on kuvaaja, jossa ei ole parittomia syklejä; Vastaavasti se on kaavio, joka voidaan värittää oikein kahdella värillä. Kaksipuoliset kuvaajat kirjoitetaan usein $G = (U, V, E),$ missä $U$ ja $V$ ovat kunkin värin kärkipisteiden osajoukkoja. Kuitenkin, ellei kaaviota ole yhdistetty, sillä ei ehkä ole ainutlaatuista 2-väriä.
kaksisuuntainen: Biregular kaavio on kaksiosainen kaavio, jossa on vain kaksi erilaista piste astetta, yksi kunkin joukon kärki bipartition.
lohko: 1. Kaavion $G$ lohko on maksimi alikuvaaja, joka on joko eristetty kärki, sillan reuna tai 2-kytketty osakaavio. Jos lohko on 2-kytketty, jokainen sen kärkipari kuuluu yhteiseen sykliin. Kaavion jokainen reuna kuuluu täsmälleen yhteen lohkoon.; 2. Kaavion $G$ lohkokaavio on toinen kuvaaja, jonka kärkipisteet ovat $G:$ n lohkoja ja jonka reuna yhdistää kaksi kärkeä, kun vastaavat lohkot jakavat nivelpisteen; eli se on $G:$ n lohkojen leikkauskuvaaja . Minkä tahansa kaavion lohkokaavio on metsä .; 3. lohko-leikkaus (tai lohko-cutpoint) kuvaaja kuvaaja, $G$ on kaksiosaisen graafin kaaviota, jossa yksi partite sarja koostuu cut-kärkipisteet $G$ , ja toinen on piste jokaista lohkoa ja $G$ . Kun $G$ on yhdistetty, sen lohkoleikkauspistegraafi on puu. ${\ displaystyle b_ {i}}$ ${\ displaystyle B_ {i}}$; 4. Lohkokaavio (jota kutsutaan myös napsautuspuuksi, jos se on kytketty, ja joskus kutsutaan virheellisesti Husimi -puuksi) on kuvaaja, jonka kaikki lohkot ovat täydellisiä kaavioita. Metsä on lohko kaavio; joten erityisesti minkä tahansa kaavion lohkokaavio on lohkokaavio, ja jokainen lohkokaavio voidaan rakentaa kuvaajan lohkokaavioksi.
sidos: Minimaalinen leikkaus-sarja : joukko reunoja joiden poistaminen katkaisee kuvaaja, josta ei osajoukko on sama ominaisuus.
kirja: 1. Kirja , kirjan kuvaaja tai kolmionmuotoinen kirja on täydellinen kolmikantakuvaaja $K 1,1, n$ ; kokoelma $n$ kolmioita, jotka on liitetty jaettuun reunaan.; 2. Toinen kuvaaja, jota kutsutaan myös kirjaksi tai nelikulmaiseksi kirjaksi, on kokoelma $4$ -sykliä, jotka on liitetty jaettuun reunaan; reunan tähden tähden suorakulmainen tuote.; 3. Kirjan upottaminen on kaavion upottaminen topologiseen kirjaan, tila, joka muodostuu yhdistämällä puolitasojen kokoelma jaettua linjaa pitkin. Yleensä upotuksen kärkien on oltava linjalla, jota kutsutaan upotuksen selkärankaksi, ja upotuksen reunojen on oltava yhdellä puolitasolla, joka on yksi kirjan sivuista.
paastaa: Karhunvatukka on kokoelma keskenään koskettaa liitetyn subgraphs, jossa kaksi subgraphs kosketa jos niillä on kärkipiste tai kukin sisältää yhden päätepisteen reunan. Bramble -järjestys on pistejoukon pienin koko, jolla on tyhjä leikkaus kaikkien osakaavioiden kanssa. Kaavion puuleveys on minkä tahansa sen bramble -enimmäisjärjestys.
haara-hajoaminen: Haara-hajoaminen ja $G$ on hierarkkinen ryhmittely reunojen $G$ , jota edustaa juurtumattomilla binaarisen puun lehdistä leimattu reunojen $G$ . Leveys haara-hajoaminen on suurin, yli reunat $e$ tämän binaarisen puun, on useita yhteisiä pisteiden välillä subgraphs määritetty reunojen $G$ kahdessa alipuut erotettu $e$ . Branchwidth on $G$ on pienin leveys tahansa haara-hajoaminen $G$ .
haaran leveys: Katso haaran hajoaminen .
silta: 1. Silta , kantapää tai leikkausreuna on reuna, jonka poistaminen katkaisee kaavion. Sillaton kuvaaja on graafinen, jolla ei ole siltoja; vastaavasti 2-reunaan yhdistetty kuvaaja.; 2. Erityisesti tasomaisuustestien yhteydessä syklin silta on maksimiosa, joka on irrotettu syklistä ja jossa kumpikin reuna kuuluu polulle, joka on sisäisesti irti syklistä. Sointu on yhden reunan silta. Reuna sykli on sykli, jossa on korkeintaan yksi silta; sen on oltava kasvot sen kaavion tasomaisessa upotuksessa.; 3. Syklin silta voi tarkoittaa myös polkua, joka yhdistää kaksi syklin huippua, mutta on lyhyempi kuin jompikumpi polusta, jotka yhdistävät samat kaksi huippua. Silloittuneet kaavio on graafinen esitys, jossa jokainen sykli neljän tai useamman kärjet on silta.
sillaton: Sillattoman kaavio on graafinen esitys, joka ei ole silta reunat; eli 2-reunaan yhdistetty kuvaaja .
perhonen: 1. Perhosgraafissa on viisi kärkeä ja kuusi reunaa; sen muodostaa kaksi kolmiota, joilla on sama kärki.; 2. Perhosverkko on kuvaaja, jota käytetään hajautetun tietojenkäsittelyn verkkoarkkitehtuurina ja joka liittyy läheisesti kuutioon yhdistettyihin sykleihin .

C

C: $C n$ on $n$ -vertex syklin kaavio ; katso sykli .
kaktus: Kaktus kaavio , kaktus puu, kaktus, tai Husimi puu on liitetty graafinen kuvaaja, jossa kunkin reunan kuuluu enintään yksi sykli. Sen lohkot ovat sykliä tai yksittäisiä reunoja. Jos lisäksi jokainen kärki kuuluu enintään kahteen lohkoon, sitä kutsutaan joulukaktukseksi.
häkki: Häkki on säännöllinen kuvaajan pienin mahdollinen jotta sen ympärysmitta.
kanoninen
kanonisointi: Kanoninen muoto kuvaajan on invariantti, että kaksi graafia on yhtä invariants jos ja vain jos ne ovat isomorfinen. Kaanonisia muotoja voidaan kutsua myös kanonisiksi muuttujiksi tai täydellisiksi muuttujiksi, ja ne määritellään toisinaan vain tietyn kuvaajaperheen kaavioille. Graafinen kanonisointi on kanonisen muodon laskentaprosessi.
kortti-: Graafi, joka on muodostettu tietystä graafista poistamalla yksi kärki, erityisesti rekonstruktio -olettamusten yhteydessä . Katso myös kansi , kaavion kaikkien korttien multisetit.
veistoksen leveys: Leikkausleveys on käsite kuvaajan leveydestä, joka on analoginen haaraleveyden kanssa, mutta jossa käytetään hierarkkisia kärkipisteitä klippejä reunojen hierarkisten ryhmittymien sijasta.
toukka: Toukka puu tai toukka on puu, jossa sisäinen solmut aiheuttaa polku.
keskusta: Keskus graafin on joukko solmuja ja vähintään epäkeskisyyden .
ketju: 1. Synonyymi kävelylle .; 2. Sovellettaessa menetelmiä algebrallisesta topologiasta kaavioihin ketjukompleksin elementti , nimittäin kärkipiste tai reunajoukko.
Cheeger vakio: Katso laajennus .
kirsikka: Kirsikka on polku kolmessa kärjessä.
χ: $χ (G)$ (kreikkalaista kirjainta chi käyttäen) on $G:$ n kromaattinen lukuja $χ' (G)$ on sen kromaattinen indeksi; katso kromaattinen ja väritys .
lapsi: On juurtunut puu, lapsi kärkipisteen $v$ on naapuri $v$ pitkin lähtevän reuna, joka on suunnattu poispäin juuri.
sointu
sointuinen: 1. Syklin sointu on reuna, joka ei kuulu sykliin, jonka molemmat päätepisteet kuuluvat sykliin.; 2. Kordiaalikuvaaja on kuvaaja, jossa jokaisessa neljän tai useamman kärjen syklissä on sointu, joten ainoat indusoidut syklit ovat kolmioita.; 3. Voimakkaasti sointukuvaaja on sointokuvio, jossa jokaisella kuuden tai useamman jakson syklillä on pariton sointu.; 4. Akordinen kaksipuolinen kuvaaja ei ole sointu (ellei se ole metsä); se on kaksipuolinen kuvaaja, jossa jokaisella kuuden tai useamman kärjen syklillä on sointu, joten ainoat indusoidut syklit ovat 4-sykliä.; 5. Ympyrän sointu on suora segmentti, joka yhdistää kaksi ympyrän pistettä; leikkauspiste kuvaajan kokoelma sointuja kutsutaan ympyrä kuvaaja .
kromaattinen: Väritys; katso väri . Kromaattinen kuvaajateoria on graafin väritysteoria. Kromaattinen numero $χ (G)$ on pienin määrä värejä tarvitaan asianmukaisen väritys on $G$ . $χ "(G)$ on kromaattinen indeksi on $G$ , vähimmäismäärä värejä tarvitaan asianmukaisen reuna väritys ja $G$ .
valittavissa
valittavuus: Kaavio on $k$ -kelpoinen, jos siinä on luetteloväritys aina, kun jokaisella kärjellä on luettelo $k$ käytettävissä olevista väreistä. Kaavion valittavuus on pienin $k$ , jolle se on $k$ -valittavissa.
ympyrä: Ympyrä kuvaaja on leikkauspiste kuvaajan sointuja ympyrän.
piiri: Piirissä voi viitata suljettu polku tai osa syklin tila (Eulerin virittävä aligraafi). Piiri sijoitus graafin on ulottuvuus sen jakson tilaa.
ympärysmitta: Ympärysmitta graafin on pituus sen pisin Yksinkertainen sykli. Kaavio on hamiltonilainen silloin ja vain, jos sen ympärysmitta on yhtä suuri kuin sen järjestys.
luokka: 1. Kaavioiden luokka tai kuvaajaperhe on (yleensä loputon) kuvaajakokoelma, joka usein määritellään kuvaajaksi, jolla on tietty ominaisuus. Sanaa "luokka" käytetään "joukon" sijasta, koska kuvaajat eivät yleensä ole joukkoja, ellei ole tehty erityisiä rajoituksia (kuten rajoitetaan pisteiden piirtämistä tietystä joukosta ja määritellään reunat kahden pisteiden joukkoiksi) kun se on virallistettu joukkoteorian avulla.; 2. Värillisen kuvaajan väriluokka on joukko pisteitä tai reunoja, joilla on yksi tietty väri.; 3. Vizingin lauseen yhteydessä yksinkertaisten kaavioiden reunojen värjäyksessä kuvaajan sanotaan olevan luokkaa yksi, jos sen kromaattinen indeksi on yhtä suuri kuin sen suurin aste, ja luokka kaksi, jos sen kromaattinen indeksi on yksi plus aste. Vizingin lauseen mukaan kaikki yksinkertaiset kuvaajat ovat joko luokkaa yksi tai luokkaa kaksi.
kynsiä: Kynsiä on puu yhden sisäisen Vertex ja kolme lehteä, tai vastaavasti täydellinen kaksijakoinen verkko $K 1,3$ . Kynsiä-free-kuvaaja on kuvaaja, joka ei ole indusoitu aligraafi joka on kynsiä.
klikki: Klikki on joukko vierekkäisten pisteiden (tai koko aligraafi indusoima että sarja). Joskus klikki määritellään keskinäisesti vierekkäisten pisteiden (tai maksimaalisen täydellisen osakaavion) maksimijoukkoksi, joka ei ole osa suurempaa tällaista joukkoa (tai osakaaviota). $K$ -clique on klikki järjestyksessä $k$ . Klikki numero $κ (G)$ graafin $G$ on suuruusluokkaa sen suurin klikki. Klikki kaavio on leikkauspiste kuvaajan maksimaalisen klikkien. Katso myös biclique , täydellinen kahden osapuolen alakuvaaja .
klikki puu: Lohkokaavion synonyymi .
klikin leveys: Klikki-leveys graafin $G$ on pienin määrä erillisten etikettien tarvitaan rakentaa $G$ , jonka toiminnot, jotka luovat merkitty kärki, muodostaa disjoint liitto kaksi leimattua kaavioita, lisää reuna yhdistää kaikki parit pisteiden kanssa tietyn tarroja, tai nimetä uudelleen kaikki kärkipisteet, joilla on tietty nimi. Kaaviot, joiden klikkausleveys on enintään $2,$ ovat täsmälleen kuvioita .
suljettu: 1. Suljettu naapurusto on se, joka sisältää sen keskipisteen; katso naapurusto .; 2. Suljettu kävely on kävely, joka alkaa ja päättyy samasta pisteestä; katso kävelyä .; 3. Kaavio on väliaikaisesti suljettu, jos se vastaa omaa transitiivista sulkemistaan; nähdä transitiivinen .; 4. Kaavio -ominaisuus suljetaan jonkin kuvaajan toiminnon alla, jos aina, kun toiminnon argumentilla tai argumentilla on ominaisuus, niin myös tulos. Esimerkiksi perinnölliset ominaisuudet sulkeutuvat indusoitujen alakuvausten alle; yksitoikkoiset ominaisuudet on suljettu osakaavioiden alle; ja pieniä suljettuja kiinteistöjä suljetaan alaikäisten alaisuudessa.
päättäminen: 1. Katso suunnatun kuvaajan transitiivinen sulkeminen kohdasta transitiivinen .; 2. Suunnatun kuvaajan sulkeminen on joukko pisteitä, joilla ei ole lähteviä reunoja sulkemisen ulkopuolelle. Esimerkiksi pesuallas on yhden pisteen sulkeminen. Sulkeminen ongelma on ongelma löytää sulkemisen minimi tai maksimi paino.
yhteistyö-: Tällä etuliitteellä on erilaisia merkityksiä, jotka yleensä sisältävät komplementtikaavioita . Esimerkiksi kuvaaja on kuvaaja, joka on tuotettu operaatioilla, jotka sisältävät täydentämisen; cocoloring on väritys, jossa kukin kärki indusoi joko riippumaton joukko (kuten oikea väriaineita) tai klikki (kuten värjäävää komplementin).
väri-
väritys: 1. Kaavion väritys on kuvaajan kärkipisteiden merkitseminen tietyn värisarjan elementeillä tai vastaavasti pisteiden osio osajoukoiksi, joita kutsutaan "väriluokiksi", joista jokainen liittyy johonkin väreistä.; 2. Jotkut kirjoittajat käyttävät "väritystä" ilman pätevyyttä tarkoituksenmukaisella värityksellä, joka antaa eri värit kunkin reunan päätepisteille. Kaaviovärityksessä tavoitteena on löytää oikea väri, joka käyttää mahdollisimman vähän värejä. Esimerkiksi kaksipuoliset kuvaajat ovat kaavioita, joissa on vain kaksi väriä, ja neljän värin lause sanoo, että jokainen tasomainen kuvaaja voidaan värjätä korkeintaan neljällä värillä. Kaavion sanotaan olevan $k$ -värinen, jos se on värjätty (oikein) $k$ väreillä, ja $k$ -värillinen tai $k$ -kromaattinen, jos tämä on mahdollista.; 3. Monia värivaihtoehtoja on tutkittu, mukaan lukien reunojen värjäys (reunojen värjäys siten, ettei kahta reunaa, joilla on sama päätepiste) jakavan värin), luetteloväritys (oikea väritys, jossa jokainen kärki rajoittuu käytettävissä olevien värien osajoukkoon), asyklinen väritys (jokainen kaksivärinen alikuva on asyklinen), rinnakkaisväritys (jokainen väriluokka indusoi itsenäisen sarjan tai klikin), täydellinen väritys (jokaisella väriluokalla on sama reuna) ja kokonaisväritys (sekä reunat että kärjet ovat värillisiä).; 4. Kaavion väritysluku on yksi plus rappeuma . Sitä kutsutaan niin, koska ahneella väritysalgoritmilla kaavion rappeutumisjärjestykseen käytetään korkeintaan tätä monta väriä.
vertailtavuutta: Ohjaamaton kuvaaja on vertailukelpoinen kuvaaja, jos sen kärkipisteet ovat osittain järjestetyn joukon elementtejä ja kaksi pistettä ovat vierekkäisiä, kun ne ovat vertailukelpoisia osittaisessa järjestyksessä. Vastaavasti vertailtavuuskäyrä on kuvaaja, jolla on transitiivinen suunta. Monet muut kuvaajaluokat voidaan määritellä erityistyyppisten osittaisjärjestysten vertailukelpoisuuskaavioiksi.
täydentää: Komplementti kaavio on yksinkertainen kaavio $G$ on toinen kaavio samalla kärki asettaa kuin $G$ , ja reuna kullekin kaksi pistettä, jotka eivät ole viereisen $G$ . ${\ displaystyle {\ bar {G}}}$
saattaa loppuun: 1. Täydellinen kuvaaja on graafi , jossa joka toinen piste on vierekkäin: kaikki mahdolliset reunat ovat läsnä. Täydellinen kuvaaja, jossa on $n$ kärkipistettä, merkitään usein $K n: ksi$ . Täydellinen kaksijakoinen verkko on sellainen, jossa jokainen kaksi pistettä vastakkaisille puolille osio pisteiden ovat vierekkäin. Täydellinen kaksipuolinen kuvaaja , jonka osion toisella puolella $on$ kärkeä ja toisella puolella $b$ kärkeä, on usein merkitty $K a, b$ . Samaa terminologiaa ja merkintöjä on laajennettu myös täydentämään moniosaisia kaavioita , kaavioita, joissa kärkipisteet on jaettu useampaan kuin kahteen osajoukkoon ja jokainen eri osajoukkojen kärkipari ovat vierekkäin; jos numerot kärkipisteet osajoukkoja ovat $,$ $b$ $,$ $c$ $, ...$ sitten tämä kuvaaja on merkitty $K$ $,$ $b$ $,$ $c$ $, ...$ .; 2. Tietyn kaavion täydennys on superkuvaaja, jolla on haluttu ominaisuus. Esimerkiksi akordin täydennys on superkuvaaja, joka on sointukuvaaja.; 3. Täydellinen vastaavuus on täydellisen sovituksen synonyymi ; katso vastaavaa .; 4. Täydellinen väritys on oikea väri, jossa kutakin väriparia käytetään vähintään yhden reunan päätepisteisiin. Jokainen väritys, jolla on vähimmäismäärä värejä, on valmis, mutta saattaa olla olemassa täydellisiä värejä suuremmilla väreillä. Akromaattinen määrä graafin on maksimimäärä värien täydellisen väritys.; 5. Kaavion täydellinen invariantti on synonyymi kanoniselle muodolle, invariantille, jolla on eri arvot ei-isomorfisille kaavioille.
komponentti: Kytketty komponentti on kuvaaja, on maksimaalinen yhdistetty aligraafi. Termiä käytetään myös kuvaajan kärkipisteiden suurimpiin osakaavioihin tai osajoukkoihin, joilla on jonkin verran korkeampi yhteysaste, mukaan lukien kaksoiskytketyt komponentit , kolmikytketyt komponentit ja vahvasti kytketyt komponentit .
tiivistyminen: Kondensaatio on suunnattu graafi $G$ on suunnattu asyklinen kuvaajan yksi kärkipiste kunkin vahvasti kytketty komponentti $G$ , ja reuna parien kytkemiseksi komponentteja, jotka sisältävät kaksi päätepistettä ainakin yhdellä reunalla $G$ .
kartio: Kaavio, joka sisältää universaalin kärjen .
kytkeä: Syy kytkeä .
kytketty: Kytketty kaavio on sellainen, jossa kunkin parin pisteiden muodostaa päätepisteet polku. Korkeammat yhteysmuodot sisältävät vahvan liitettävyyden suunnatuissa kaavioissa (kullakin kahdella pisteellä on polkuja yhdestä toiseen molempiin suuntiin), $k$ -pisteeseen yhdistetyt kuvaajat (alle $k$ pisteen poistaminen ei voi katkaista kuvaajaa) ja $k$ -reuna -liitetyt kuvaajat (alle $k$ reunan poistaminen ei voi irrottaa kaaviota).
keskustella: Käänteiskaavio on synonyymi transponointikaavalle; katso transponoi .
ydin: 1. $K$ -piste on indusoitu osakaavio, joka on muodostettu poistamalla kaikki pisteet, joiden aste on pienempi kuin $k$ , ja kaikki pisteet, joiden aste on pienempi kuin $k$ aiempien poistojen jälkeen. Katso rappeuma .; 2. ydin on kaavio $G$ siten, että jokainen kaavio homomorfismi kohteesta $G$ itseensä on isomorfismi.; 3. Kaavion $G$ ydin on minimaalinen kuvaaja $H$ siten, että on olemassa homomorfismeja $G:$ stä $H: iin$ ja päinvastoin. $H$ on ainutlaatuinen isomorfismiin asti. Se voidaan esittää indusoituna $G-$ osakaaviona , ja se on ydin siinä mielessä, että kaikki sen itsehomomorfismit ovat isomorfismeja.; 4. Graafin täsmäytymisteoriassa kuvaajan ydin on osa sen Dulmage – Mendelsohn -hajoamista , joka muodostuu kaikkien suurimpien täsmäytysten liitoksena.
Cotree: 1. Jännittävän puun täydennys .; 2. Juurtunut puurakenne , jota käytetään kuvaamaan kuvaajaa , jossa kukin käyrän kärki on puun lehti, jokaisen puun sisäinen solmu on merkitty 0: lla tai 1: llä ja kaksi kuvaajan kärkeä ovat vierekkäin, jos ja vain jos niiden alin yhteinen puun esi -isä on merkitty 1.
peite: Kärki kansi on joukko solmuja tapauksesta jokaiseen reunaan kuvaajan. Reunapäällys on joukko reunoja tapahtuman joka kärkeen kuvaajan. Kaavion osakaaviojoukko kattaa kyseisen kuvaajan, jos sen liitto- otettuna pisteiden ja reunojen suhteen-on yhtä suuri kuin kuvaaja.
kriittinen: Tietyn ominaisuuden kriittinen kuvaaja on kuvaaja, jolla on ominaisuus, mutta sellainen, että jokaisella yksittäisellä kärkipisteellä poistamalla muodostetulla alikuvaajalla ei ole ominaisuutta. Esimerkiksi tekijäkriittinen kuvaaja on sellainen, jolla on täydellinen sovitus (1-kerroin) jokaiselle kärkipisteen poistolle, mutta (koska sillä on pariton määrä pisteitä) sillä ei ole täydellistä sovitusta. Vertaa hypo- , jota käytetään kaavioissa, joilla ei ole ominaisuutta, mutta joilla on yksi yhden pisteen poisto.
kuutio
kuutiometriä: 1. Kuutiokaavio , kuution pisteiden ja reunojen kahdeksanpisteinen kuvaaja.; 2. Hyperkuutiokaavio , kuutiokaavion yleisempi yleistys.; 3. Taitettu kuutiokaavio , joka on muodostettu hyperkuutosta lisäämällä vastaavat vastakkaiset kärkipisteet.; 4. puolittunut kuutio kaavio , puoli-neliö on hyperkuution kuvaajan.; 5. Osittainen kuutio , hyperkuution etäisyyttä säilyttävä alakuvaaja.; 6. Kaavion $G$ kuutio on kuvaajan teho $G 3$ .; 7. Kuutiokuvaaja , toinen $3$ -säännöllisen kuvaajan nimi , jossa jokaisella kärjellä on kolme tulevaa reunaa.; 8. Kuutioon yhdistetyt syklit , kuutiomainen kuvaaja, joka muodostetaan korvaamalla hyperkuution jokainen kärki syklillä.
leikata
leikkaussetti: Leikkaus on osio pisteiden kuvaajan kahteen osajoukkoja, tai asettaa (tunnetaan myös leikkaus-sarja) on reunat, jotka ulottuvat osiolle, jos joukko on ei-tyhjä. Reunan sanotaan kattavan osion, jos sillä on päätepisteet molemmissa osajoukoissa. Siten leikkausjoukon poistaminen yhdistetystä kaaviosta katkaisee sen.
leikkauspiste: Katso artikulaatiokohta .
leikkaa tilaa: Leikattu tila on kuvaaja on GF (2) - vektori tila , jonka cut-sarja s kuvaajan sen elementtejä ja symmetrinen ero sarjaa kuin sen vektori lisäksi toimintaa.
sykli: Sykli voi joko viitata suljettu kävellä (kutsutaan myös kiertueen ) tai tarkemmin suljettuun kävellä ilman toistuvaa pisteet ja siten reunat (kutsutaan myös yksinkertaisen sykli). Kummassakin tapauksessa ensimmäisen kärjen valintaa pidetään yleensä merkityksettömänä: kävelyn sykliset permutaatiot tuottavat saman syklin. Tärkeitä syklien erityistapauksia ovat Hamiltonin syklit , indusoidut syklit , perifeeriset syklit ja lyhin sykli, joka määrittää kaavion ympärysmitan . $K$ Ensimmäinen solunsalpaajahoitojakso on sykli, jonka pituus on $k$ ; esimerkiksi $2$ -sykli on digoni ja $3$ -sykli on kolmio. Sykli kaavio on graafinen esitys, joka on itsessään yksinkertainen sykli; sykli kuvaajan $n$ kärjet on yleisesti merkitty $C n$ . Sykli tila on vektori tila syntyy yksinkertainen sykliä kuvaajan.

D

DAG: Lyhenne suunnatusta asyklisestä kaaviosta , suunnattu kuvaaja ilman suunnattuja syklejä.
laivan kansi: Kaavioiden joukko muodostettiin yhdestä kuvaajastä $G$ poistamalla yksi kärki kaikilla mahdollisilla tavoilla, erityisesti rekonstruktio -olettamusten yhteydessä . Reuna-kansi muodostetaan samalla tavalla poistamalla yksi reuna kaikilla mahdollisilla tavoilla. Pakan kaavioita kutsutaan myös kortteiksi . Katso myös kriittiset (kaaviot, joilla on ominaisuus, jota mikään kortti ei hallitse) ja hypo- (kaaviot, joissa ei ole kaikkien korttien hallussa olevaa ominaisuutta).
hajoaminen: Katso puun hajoaminen , polun hajoaminen tai haaran hajoaminen .
rappeutua
rappeutuminen: $K$ -degenerate kaavio on suuntaamattoman graafin, jossa jokainen indusoi aligraafi on vähintään korkeintaan astetta $k$ . Degeneraatio graafin on pienin $k$ , jota varten se on $k$ -degenerate. Degeneraatiojärjestys on pisteiden järjestys siten, että kullakin kärkipisteellä on vähimmäisaste sen ja kaikkien myöhempien kärkipisteiden indusoidussa osakaaviossa; $k$ -rappeutuneen kuvaajan rappeutumisjärjestyksessä jokaisella kärjellä on enintään $k$ myöhempiä naapureita. Degeneraatio tunnetaan myös nimellä $k$ -pisteet, leveys ja kytkentä, ja yhtä plus degeneraatiota kutsutaan myös väritysluvuksi tai Szekeres -Wilf -numeroksi. $k$ -degeneroitua kuvaajaa on kutsuttu myös $k$ -induktiiviseksi kuvaajaksi.
tutkinto: 1. Kaavion kärjen aste on sen tulevien reunojen lukumäärä. Kaavion $G$ aste (tai sen suurin aste) on sen pisteiden asteiden maksimi, usein merkitty $Δ (G)$ ; vähimmäispuhtausaste $G$ on vähintään sen kärki astetta, usein merkitään $δ (G)$ . Tutkintoa kutsutaan joskus valenssiksi ; $v$ : n aste $G: ssä$ voidaan merkitä $d G (v)$ , $d (G)$ tai $deg (v)$ . Kokonaisaste on kaikkien pisteiden asteiden summa; jonka kättely Aine on parillinen määrä. Aste sekvenssi on kokoelma astetta kaikki pisteet, luokitellussa järjestyksessä suurimmasta pienimpään. Suunnatussa kaaviossa voidaan erottaa sisään-aste (saapuvien reunojen määrä) ja ulos-aste (lähtevien reunojen määrä).; 2. Kaavion homomorfismiaste on synonyymi sen Hadwiger -numerolle , joka on suurimman klikin alaikäinen.
Δ, δ: $Δ (G)$ (käyttäen kreikkalaista kirjainta delta) on kärkipisteen suurin aste $G$ : ssä ja $δ (G)$ on vähimmäisaste; katso tutkinto .
tiheys: Kaaviossa, jossa on n solmua, tiheys on kaavion reunojen lukumäärän suhde kokonaisen kuvaajan reunojen määrään n solmussa. Katso tiheä kaavio .
syvyys: Juurtuneen puun solmun syvyys on juurien ja solmun välisen polun reunojen määrä. Esimerkiksi juuren syvyys on 0 ja minkä tahansa sen viereisen solmun syvyys on 1. Se on solmun taso miinus yksi. Huomaa kuitenkin, että jotkut kirjoittajat käyttävät sen sijaan syvyyttä solmun tason synonyyminä .
halkaisija: Yhdistetyn kaavion halkaisija on lyhyimmän polun enimmäispituus . Toisin sanoen se on käyrän kärkiparien välisten etäisyyksien suurin. Jos kaavion reunoilla on painoja, sen painotettu halkaisija mittaa reitin pituuden reitin painojen summan verran polkua pitkin, kun taas painottamaton halkaisija mittaa polun pituuden reunoiden lukumäärällä. Irrotettujen kaavioiden määritelmät vaihtelevat: halkaisija voidaan määritellä äärettömäksi tai liitetyn komponentin suurimmaksi halkaisijaksi tai se voi olla määrittelemätön.
timantti-: Timantti kaavio on suuntaamattoman graafin, jossa on neljä pistettä ja sen viiteen reunaan.
diconnected: Vahva ly kytketty . (Ei pidä sekoittaa irrotettuun )
digon: Digonin on yksinkertainen sykli, jonka pituus on kaksi suunnatun verkon tai multigraph. Digoneja ei voi esiintyä yksinkertaisissa suunnattomissa kaavioissa, koska ne vaativat saman reunan toistamista kahdesti, mikä rikkoo yksinkertaisen määritelmää .
digraph: Synonyymi suunnatulle kuvaajalle .
dipath: Katso suunnattu polku .
suora edeltäjä: Suunnatun reunan häntä, jonka pää on annettu kärki.
suora seuraaja: Suunnatun reunan pää, jonka häntä on annettu kärki.
ohjattu: Suunnattu graafi on sellainen, jossa reunat on erottaa suuntaan, yksi kärki toiseen. On sekoitettu kuvaaja , joka on suunnattu reuna on jälleen yksi, joka on erotettava suuntaan; suunnattuja reunoja voidaan kutsua myös kaariksi tai nuoliksi.
suunnattu kaari: Katso nuoli .
suunnattu reuna: Katso nuoli .
suunnattu linja: Katso nuoli .
suunnattu polku: Polku , jossa kaikki reuna s on sama suunta . Jos suunnattu polku johdot kärki $x$ solmuun $y$ , $x$ on edeltäjä on $y$ , $y$ on seuraaja on $x$ , ja $y$ on sanottu olevan tavoitettavissa peräisin $x$ .
suunta: 1. epäsymmetrinen suhde kahden vierekkäisen kärkipisteet on kaavio , edustettuna nuoli .; 2. Epäsymmetrinen suhde kahden kärjen välillä suunnatulla polulla .
katkaista: Syy irrotettavaksi .
katkaistu: Ei kytketty .
hajottaa: 1. Kaksi aligrafiikkaa ovat reunaerot, jos niillä ei ole reunoja, ja kärkipisteet, jos niillä ei ole pisteitä.; 2. disjoint unionin kahden tai useamman kuvaajat on kaavio, jonka kärki ja reuna asetetaan ovat disjoint ammattiliitot vastaavan sarjaa.
etäisyys: Etäisyys minkä tahansa kahden pisteiden kuvaaja, on pituus lyhin polku, jolla on kaksi pistettä, kuten sen päätepisteet.
domaattinen: Kaavion domaattinen osio on pisteiden osio hallitseviksi joukkoiksi. Domatic määrä kuvaajan on maksimimäärä dominoi setit osiolle.
hallitseva: Dominoi joukko on joukko solmuja, joka sisältää tai on lähellä joka kärkeen kaavion; ei pidä sekoittaa pisteiden kansiin, joka on käyrän kaikkien reunojen kohde. Tärkeitä hallitsevien joukkojen erityistyyppejä ovat itsenäiset hallitsevat joukot (hallitsevat joukot, jotka ovat myös itsenäisiä joukkoja) ja toisiinsa liittyvät hallitsevat joukot (hallitsevat joukot, jotka indusoivat kytkettyjä osakaavioita). Yksipisteistä hallitsevaa joukkoa voidaan kutsua myös universaalipisteeksi. Kaavion hallitseva numero on pisteiden määrä pienimmässä hallitsevassa joukossa.

E

E: $E (G)$ on $G: n reunajoukko$ ; katso reunasarja .
korva: Kaavion korva on polku, jonka päätepisteet voivat osua yhteen, mutta joissa muuten ei ole kärkipisteitä tai reunoja.
korvan hajoaminen: Korva hajoaminen on osio reunojen kuvaajan jonoksi korvat, jonka jokainen päätepisteiden (ensimmäisen jälkeen) kuuluvat edelliseen korvaan ja joiden kunkin sisäpisteiden eivät kuulu Jonkin edellisen korvaan. Avoin korva on yksinkertainen polku (korva, jossa ei ole toistuvia kärkiä), ja avoin korvan hajoaminen on korvan hajoaminen, jossa jokainen korva ensimmäisen jälkeen on auki; kaaviossa on avoin korvan hajoaminen silloin ja vain, jos se on kaksoiskytketty. Korva on pariton, jos sillä on pariton määrä reunoja, ja pariton korvan hajoaminen on korvan hajoaminen, jossa jokainen korva on pariton; kaaviossa on pariton korvan hajoaminen silloin ja vain, jos se on tekijäkriittinen.
eksentrisyys: Pisteen epäkeskisyys on kauimpana etäisyydestä mihin tahansa muuhun pisteeseen.
reuna: Reuna on (yhdessä pisteiden kanssa) yksi kahdesta perusyksiköstä, joista kuvaajat rakennetaan. Jokaisella reunalla on kaksi (tai hypergraafissa enemmän) kärkeä, joihin se on kiinnitetty, nimeltään sen päätepisteet. Reunat voivat olla suunnattuja tai suunnattomia; suunnattomia reunoja kutsutaan myös viivoiksi ja suunnattuja reunoja kutsutaan myös kaariksi tai nuoliksi. Ohjaamattomassa yksinkertaisessa kaaviossa reuna voidaan esittää sen kärkipisteiden joukkona ja suunnatussa yksinkertaisessa kuvaajassä se voidaan esittää sen kärkipisteiden järjestettynä parina. Reuna, joka yhdistää pisteet $x$ ja $y,$ kirjoitetaan joskus $xy$ .
reunan leikkaus: Joukko reuna s joiden poistaminen katkaisee kuvaaja . Yhden reunan leikkausta kutsutaan siltaksi , kannakseksi tai leikkausreunaksi .
reunasarja: Annetun kuvaajan $G$ reunojen joukko , jota joskus merkitään $E (G): llä$ .
reunaton kaavio: Reunattomissa kuvaajan tai kokonaan irronnut kuvaaja tietyllä joukko solmuja on kaavio, jossa ei ole reunoja. Sitä kutsutaan joskus tyhjäksi kuvaajaksi, mutta tämä termi voi viitata myös kuvaajaan, jolla ei ole kärkipisteitä.
upottaminen: Kaavio upottamisen on topologinen esitys kaavion osajoukko topologinen tilaa kunkin kärki on piste, kunkin reunan edustettuina käyrä, jonka päätepisteet reunan päätepisteet käyrä, ja mikään muu välisiä risteyksiä pisteiden tai reunat. Tasomainen kaavio on graafinen esitys, joka on tällainen upotus päälle euklidinen taso, ja toroidaalisen kaavio on graafinen esitys, joka on sellainen upotus päälle torus. Suvun graafin on pienin mahdollinen suvun kaksiulotteisen moninaiset , johon se voidaan upottaa.
tyhjä kaavio: 1. Reunaton kuvaaja tyhjässä kärkipisteessä.; 2. Järjestys nolla kuvaaja , kuvaaja, jossa ei ole pisteitä eikä reunoja.
loppuun: Lopussa äärettömän kaavio on vastaavuus luokka säteitä, jossa kaksi sädettä ovat yhtä jos on kolmasosa säde, joka sisältää äärettömän monta ääripisteitä molemmat.
päätepiste: Yksi kahdesta kärjestä, joita yhdistää tietty reuna, tai yksi kävelyn, polun tai polun ensimmäisestä tai viimeisestä kärjestä. Tietyn suunnatun reunan ensimmäistä päätepistettä kutsutaan hännäksi ja toista päätepistettä pääksi .
luettelointi: Kaavioiden luettelointi on ongelma laskettaessa tietyn kuvaajaluokan kuvaajat niiden järjestyksen funktiona. Yleisemmin laskentaongelmat voivat viitata joko ongelmiin tietyn yhdistelmäobjektien luokan laskemisessa (kuten klikit, riippumattomat joukot, värit tai puulajeja) tai kaikkien tällaisten objektien algoritmisessa luettelemisessa.
Eulerian: Eulerin polku on kävellä, joka käyttää jokaisen reunan kuvaaja täsmälleen kerran. Eulerian -kierros (jota kutsutaan myös Eulerian -kiertueeksi tai Euler -kiertueeksi) on suljettu kävely, joka käyttää jokaista reunaa täsmälleen kerran. Eulerian kuvaaja on kuvaaja, jossa on Eulerian piiri. Ohjaamattomalle kuvaajalle tämä tarkoittaa, että kuvaaja on yhteydessä toisiinsa ja jokaisella pisteellä on parillinen aste. Suunnatulla kuvaajalla tämä tarkoittaa sitä, että kuvaaja on vahvasti yhteydessä toisiinsa ja jokaisen kärjen aste on yhtä suuri kuin ulkoinen aste. Joissakin tapauksissa yhteysvaatimusta kevennetään, ja vain asteen vaatimukset täyttävää kuvaajaa kutsutaan Eulerianiksi.
jopa: Jaettavissa kahdella; esimerkiksi parillinen sykli on sykli, jonka pituus on parillinen.
laajennin: Laajentimen kaavio on graafinen esitys, jonka reuna laajennus, Vertex laajennus, tai spektrin laajeneminen rajoittuu nollasta poispäin.
laajentuminen: 1. reuna laajennus, isoperimetric numero, tai Cheeger vakio graafin $G$ on pienin suhde, yli osajoukot $S$ korkeintaan puoli on kärkien $G$ , ja reunojen lukumäärän jättää $S$ lukumäärään pisteiden $S$ .; 2. kärki laajennus, Vertex isoperimetric numero, tai suurennettu kaavio $G$ on pienin suhde, yli osajoukot $S$ korkeintaan puoli on kärkien $G$ , on pisteiden lukumäärä läheisyyteen sen ulkopuolelle $S$ lukumäärää pisteiden $S$ .; 3. ainutlaatuinen naapuri laajennus kuvaaja, $G$ on pienin suhde, yli osajoukot korkeintaan puoli on kärkien $G$ , on pisteiden lukumäärä ulkopuolella $S$ mutta vieressä ainutlaatuinen kärjen $S$ lukumäärään pisteiden $S$ .; 4. $D$ -säännönmukaisen kuvaajan $G$ spektraalinen laajeneminen on spektriaukko sen vierekkäismatriisin suurimman ominaisarvon $d$ ja toiseksi suurimman ominaisarvon välillä.; 5. Kaavioiden perheellä on rajallinen laajeneminen, jos kaikilla sen $r$ -matala -alaikäisillä on suhde reunoihin ja pisteisiin, joita rajoittaa funktio $r$ , ja polynomilaajennus, jos $r:$ n funktio on polynomi.

F

kasvot: Vuonna tasoverkkona tai kuvaajan upottamisen , liitetty osa osajoukko tasoon tai pintaan, upotuksen, joka on erilliset kaaviosta. Jos koneeseen upotetaan, kaikki kasvot paitsi yksi rajataan; ainoita poikkeuksellisia kasvoja, jotka ulottuvat äärettömyyteen, kutsutaan ulkopinnoiksi.
tekijä: Kaavion tekijä on ulottuva osakaavio: osakaavio, joka sisältää kaikki kuvaajan kärkipisteet. Termiä käytetään pääasiassa säännöllisten osakaavioiden yhteydessä: $k$ -tekijä on tekijä, joka on $k$ -säännöllinen. Erityisesti $1$ -tekijä on sama asia kuin täydellinen sovitus. Tekijä-kriittinen kuvaaja on kuvaaja, joka poistaa Jonkin kärki tuottaa kaavion, jossa on $1$ -tekijän.
tekijä: Kaavio tekijöihinjakoalgoritmi on osio reunojen graafi tekijät; $k$ -factorization on väliseinällä $k$ -factors. Esimerkiksi $1$ -tekijä on reunaväritys, jossa on lisäominaisuus, että jokainen kärki kohdistuu kunkin värin reunaan.
perhe: Synonyymi luokalle .
äärellinen: Kuvaaja on äärellinen, jos sillä on äärellinen määrä pisteitä ja äärellinen määrä reunoja. Monet lähteet olettavat, että kaikki kaaviot ovat äärellisiä sanomatta sitä nimenomaisesti. Kaavio on paikallisesti äärellinen, jos jokaisella kärjellä on äärellinen määrä tulevia reunoja. Ääretön kuvaaja on kuvaaja, joka ei ole äärellinen: sillä on äärettömän monta pistettä, äärettömän monta reunaa tai molemmat.
ensimmäinen tilaus: Graafien ensimmäisen kertalogiikan logiikka on eräänlainen logiikka, jossa muuttujat edustavat kuvaajan kärkipisteitä, ja on olemassa binaaripredikaatti, jolla testataan, ovatko kaksi kärkiä vierekkäisiä. Erotetaan toisen asteen logiikasta, jossa muuttujat voivat edustaa myös kärkipisteitä tai reunoja.
-läppä: Ja joukko solmuja $X$ , $X$ -flap on liitetyn laitteen indusoidun aligraafi muodostettu poistamalla $X$ . Läppien terminologiaa käytetään yleisesti turvapaikkojen yhteydessä , toimintoja, jotka kartoittavat pieniä kärkipisteitä läppiinsä. Katso myös syklin silta , joka on joko syklin kärkien läppä tai syklin sointu.
kielletty: Kielletty kuvaaja luonnehdinta on luonnehdinta perheen kuvaajat olevan kuvaajat, joilla ei ole tiettyjä muita kuvaajat subgraphs, indusoi subgraphs tai alaikäisiä. Jos $H$ on yksi käyristä, jota ei esiinny osakaaviona, indusoiduna osakaaviona tai pienenä, $H: n$ sanotaan olevan kielletty.
metsä: Metsä on suuntaamattoman graafin ilman sykliä (a disjoint liitto juurtumattomilla puut), tai suunnattu graafi, joka on muodostettu toisistaan erillään liitto juurtuneet puita.
Frucht: 1. Robert Frucht; 2. Frucht -kuvaaja , yksi kahdesta pienimmästä kuutiokuvasta, joilla ei ole epäsäännöllisiä symmetrioita.; 3. Fruchtin lause, jonka mukaan jokainen äärellinen ryhmä on äärellisen kuvaajan symmetrian ryhmä.
koko: Synonyymi indusoidulle .
toiminnallinen kaavio: Toiminnallinen kaavio on suunnattu graafi, jossa jokainen piste on out-asteen yksi. Vastaavasti funktionaalinen kuvaaja on suurin suunnattu pseudoforest.

G

G: Muuttuja, jota käytetään usein kuvaajan kuvaamiseen.
suku: Kaavion suku on pinnan vähimmäissuku, johon se voidaan upottaa; katso upottaminen .
geodeettinen: Substantiivina geodeettinen on lyhin polku . Kun sitä käytetään adjektiivina, se tarkoittaa, että se liittyy lyhyimpiin polkuihin tai lyhyimpiin polkuihin.
jättiläinen: Satunnaiskäyrien teoriassa jättikomponentti on kytketty komponentti, joka sisältää vakion murto -osan käyrän kärjistä. Satunnaiskäyrien vakiomalleissa on tyypillisesti korkeintaan yksi jättikomponentti.
ympärysmitta: Ympärysmitta graafin on pituus sen lyhimmän ajan.
kuvaaja: Graafiteorian peruskohde, pisteiden järjestelmä, jotka on yhdistetty pareittain reunoilla. Usein jaettu suunnattuihin kaavioihin tai suunnittelemattomiin kaavioihin sen mukaan, onko reunoilla suunta tai ei. Sekoitettu kaavio sisältää molempia reunoja.
ahne: Tuotettu ahneella algoritmilla . Esimerkiksi kaavion ahne väritys on väri, joka saadaan ottamalla huomioon pisteet jossakin järjestyksessä ja määrittämällä kullekin pisteelle ensimmäinen käytettävissä oleva väri.
Grötzsch: 1. Herbert Grötzsch; 2. Grötzsch-kuvaaja , pienin kolmiovapaa kuvaaja , joka vaatii neljä väriä missä tahansa oikeassa värissä.; 3. Grötzschin lause, jonka mukaan kolmiovapaat tasomaiset kuvaajat voidaan aina värittää korkeintaan kolmella värillä.
Karkea numero: 1. Kaavion Grundy-luku on ahneella värityksellä tuotettujen värien enimmäismäärä huonosti valitulla kärkipisteellä.

H

H: Muuttuja, jota käytetään usein kuvaajan kuvaamiseen, varsinkin kun toinen kuvaaja on jo merkitty $G: llä$ .
H -väritys: $H$ -coloring graafin $G$ (jossa $H$ on myös kaavio) on homomorfismi päässä $H$ ja $G$ .
H -vapaa: Kaavio on $H$ -vapaa, jos sillä ei ole indusoitua alikuvaajaa , joka on isomorfinen $H: lle$ , eli jos $H$ on kielletty indusoitu alikuvaaja. $H$ vapaata kuvaajat ovat perheen kaikki kuvaajat (tai usein, kaikki rajallinen käyrät), jotka ovat $H$ vapaata. Esimerkiksi kolmion vapaan kuvaajat ovat kaavioita, jotka eivät ole kolmio kaavio kuin aligraafi. Ominaisuus, että ne $H$ vapaata on aina perinnöllinen. Kaavio on $H$ -vähävarainen, jos sillä ei ole pientä isomorfista $H: lle$ .
Hadwiger: 1. Hugo Hadwiger; 2. Kaavion Hadwiger -luku on kaavion suurimman täydellisen molli. Sitä kutsutaan myös supistumisklikiksi tai homomorfismiasteeksi.; 3. Hadwiger -olettamus on olettamus, että Hadwiger -luku ei ole koskaan pienempi kuin kromaattinen luku.
Hamiltonilainen: Hamiltonin polku tai Hamiltonin sykli on yksinkertainen ulottuu polku tai yksinkertainen virittävä sykli: se kattaa kaikki graafin tarkalleen kerran. Kaavio on Hamiltonin, jos se sisältää Hamiltonin syklin, ja jäljitettävissä, jos se sisältää Hamiltonin polun.
paratiisi: $K$ - Haven on funktio, joka kuvaa jokaisen joukko $X$ on vähemmän kuin $k$ pisteiden yksi sen läppien, usein täytä muita johdonmukaisuus olosuhteissa. Turvasataman järjestys on numero $k$ . Havensin avulla voidaan luonnehtia äärellisten kaavioiden puuleveyttä ja äärettömien kaavioiden päitä ja Hadwiger -lukuja.
korkeus: 1. Juurtuneen puun solmun korkeus on juuren poikki kulkevan maksimireitin reunojen lukumäärä (eli sen solmujen syvyys kasvaa tarkasti), joka alkaa kyseisestä solmusta ja päättyy lehtiin.; 2. korkeus on juuret puu on korkeus sen juuri. Toisin sanoen puun korkeus on pisin mahdollinen polku, joka poistuu juurista ja joka alkaa juurista ja päättyy lehtiin.; 3. Suunnatun asyklisen kuvaajan korkeus on tämän kaavion suunnatun polun suurin pituus.
perinnöllinen: Perinnöllinen ominaisuus graafien on ominaisuus, joka on suljettu indusoidaan subgraphs: jos $G$ on perinnöllinen ominaisuus, niin täytyy jokaisen indusoidun aliverkko $G$ . Vertaa yksitoikkoista (suljettu kaikkien alakuvioiden alla) tai pienikokoista (suljettu alaikäisten alla).
kuusikulmio: Yksinkertainen sykli, joka koostuu täsmälleen kuudesta reunasta ja kuudesta kärjestä.
reikä: Reikä on indusoitu sykli, jonka pituus on neljä tai enemmän. Pariton reikä on pariton pituus. Reiänesto on indusoitu osakaavio luokasta neljä, jonka komplementti on sykli; vastaavasti se on reikä komplementtikaaviossa. Tätä terminologiaa käytetään pääasiassa täydellisten kaavioiden yhteydessä, joille on tunnusomaista vahva täydellisen kuvaajan lause, koska ne ovat kaavioita, joissa ei ole parittomia reikiä tai parittomia reikiä. Aukottomat kaaviot ovat samat kuin sointukaaviot .
homomorfinen vastaavuus: Kaksi kuvaajaa ovat homomorfisesti samanarvoisia, jos on olemassa kaksi homomorfismia, yksi kustakin kaaviosta toiseen.
homomorfismi: 1. Graafin homomorfismi on kartoitus yhden kuvaajan kärkipisteestä toisen kuvaajan pistejoukkoon, joka kartoittaa viereiset kärkipisteet viereisiin pisteisiin. Tämäntyyppinen kaavioiden välinen kartoitus on yleisimmin käytetty graafiteorian luokka-teoreettisissa lähestymistavoissa. Oikea kuvaajan väritys voidaan vastaavasti kuvata täydellisen kuvaajan homomorfismiksi.; 2. Kaavion homomorfismiaste on synonyymi sen Hadwiger -numerolle , joka on suurimman klikin alaikäinen.
hyperedge: Hypergraafin reuna , jolla on mikä tahansa määrä päätepisteitä, toisin kuin vaatimus, että kaavioiden reunoilla on täsmälleen kaksi päätepistettä.
hyperkuutio: Hyperkuution kaavio on graafinen esitys, joka on muodostettu kärjet ja reunat geometrinen hyperkuution .
hypergrafia: Hypergraph on yleistys on graafinen esitys, jossa kunkin reunan (kutsutaan hyperedge tässä yhteydessä) voi olla enemmän kuin kaksi päätepistettä.
hypo-: Tämä etuliite yhdessä kuvaajaominaisuuden kanssa osoittaa kuvaajan, jolla ei ole ominaisuutta, mutta sellainen, että jokaisella yksittäisellä kärjellä poistamalla muodostetulla alikuvaajalla on ominaisuus. Esimerkiksi hypohamiltonin kuvaaja on sellainen, jolla ei ole Hamiltonin sykliä, mutta jonka jokainen yhden kärjen poisto tuottaa Hamiltonin alikuvaajan. Vertaa kriittistä , käytetään kaavioissa, joilla on ominaisuus, mutta joilla ei ole yhden pisteen poistoa.

Minä

asteessa: Tulevien reunojen määrä suunnatussa kaaviossa; katso tutkinto .
esiintyvyys: Esiintyvyys on kaavio on kärkipiste reuna pari siten, että kärki on päätepiste reunan.
esiintyvyysmatriisi: Esiintyvyys matriisi on kuvaaja on matriisi, jonka rivit indeksoidaan graafin solmut, ja jonka sarakkeet on indeksoitu reunat, jossa on yksi solu rivin $i$ ja sarakkeen $j$ kun piste $i$ ja reuna $j$ ovat tapaus, ja muuten nolla.
tapaus: Reunan ja yhden sen päätepisteen välinen suhde.
vertaansa vailla: Vertaamattomuuskaavio on vertailukelpoisuuden kuvaajan täydennys ; katso vertailukelpoisuutta .
riippumaton: 1. Itsenäinen joukko on joukko pisteitä, jotka indusoivat reunattoman alikuvaajan. Sitä voidaan kutsua myös vakaaksi setiksi tai cocliqueksi. Riippumattomuus numero $α (G)$ on koko suurimman riippumaton joukko .; 2. Kaavion graafisessa matroidissa reunojen osajoukko on riippumaton, jos vastaava osakaavio on puu tai metsä. Vuonna bicircular matroid , osajoukko reunat on riippumaton, jos vastaava aligraafi on pseudoforest .
välinpitämättömyys: Välinpitämättömyys kaavio on toinen nimi välimatkoin kuvaajan tai yksikön väli kaavio; nähdä oikein .
aiheuttama: Indusoi aligraafi tai koko aligraafi kuvaajan on aligraafi muodostettu osajoukko pisteiden ja kaikki reunat, jotka ovat molemmat päätepisteet osajoukkoon. Erikoistapauksia ovat indusoidut reitit ja indusoidut syklit , indusoidut alikuvaajat, jotka ovat polkuja tai syklejä.
induktiivinen: Synonyymi rappeutuneelle .
ääretön: Ääretön kuvaaja ei ole äärellinen; katso rajallinen .
sisäinen: Polun tai puun kärki on sisäinen, jos se ei ole lehti; eli jos sen aste on suurempi kuin yksi. Kaksi polkua ovat sisäisesti hajanaisia (jotkut kutsuvat sitä itsenäisiksi ), jos niillä ei ole mitään yhteistä kärkeä, paitsi ensimmäinen ja viimeinen.
Risteys: 1. Kahden kuvaajan leikkauspiste on niiden suurin yhteinen alikuvaaja, kuvaaja, joka muodostuu kumpaankin kuvaajaan kuuluvista kärjistä ja reunoista.; 2. Leikkausgraafi on kuvaaja, jonka kärkipisteet vastaavat joukkoja tai geometrisia objekteja ja joiden reuna on kahden pisteen välissä täsmälleen silloin, kun vastaavilla kahdella joukolla tai objektilla on tyhjä leikkaus. Useita kuvaajaluokkia voidaan määritellä tietyntyyppisten objektien leikkauspisteiksi, esimerkiksi sointukäyrät (puun osapuiden leikkausgraafit), ympyräkaaviot ( ympyrän sointujen leikkausgraafit), intervallikaaviot ( aikaväleiden leikkausgraafit) viiva), viivakaaviot (kaavion reunojen leikkauskaaviot) ja napsautuskaaviot (kaavion maksimiklikkien leikkauspisteet). Jokainen kuvaaja on leikkauskuvaaja joillekin sarjajoukoille, ja tätä perhettä kutsutaan kaavion leikkausesitykseksi. Leikkauspiste määrä graafin $G$ on pienin alkioiden kokonaislukumäärä missä tahansa risteyksessä esitys $G$ .
väli: 1. aikaväli kaavio on leikkauspiste kaavio on välein linjan .; 2. Väli $[u, v]$ kaaviossa on kaikkien lyhyimpien polkujen yhdistäminen $u:$ sta $v: hen$ .; 3. Välin paksuus on synonyymi reitin leveydelle .
muuttumaton: Ominaisuuden synonyymi .
käänteinen nuoli: Nuoli vastakkaisella suuntaan verrattuna toiseen suuntaan. Nuoli $(y, x)$ on nuolen $(x, y)$ käänteinen nuoli .
eristetty: Kaavion eristetty kärki on piste, jonka aste on nolla, eli piste, jossa ei ole reunoja.
isomorfinen: Kaksi kuvaajaa ovat isomorfisia, jos niiden välillä on isomorfismi; katso isomorfismi .
isomorfismi: Kaavio isomorphism on yksi-yhteen esiintyvyys säilyttää vastaavuus pisteiden ja reunoista kaavion pisteiden ja reunojen toisen kuvaajan. Kaksi tällä tavalla liittyvää kuvaajaa sanotaan olevan isomorfisia.
isoperimetrinen: Katso laajennus .
kannaksen: Synonyymi silta , reunan merkityksessä, jonka poistaminen katkaisee kaavion.

K

K: Täydellisten kaavioiden, täydellisten kahden osapuolten kaavioiden ja täydellisten moniosaisten kaavioiden merkintätapa on täydellinen .
κ: $κ (G)$ (käyttäen kreikkalaista kirjainta kappa) on suurimman klikin järjestys $G: ssä$ ; katso klikki .
ydin: Suunnatun kuvaajan ydin on joukko pisteitä, jotka ovat sekä vakaita että absorboivia .
solmu: Väistämätön osa suunnattua kuvaajaa . Katso solmu (matematiikka) ja solmuteoria .

L

L: $L (G)$ on viivadiagrammi, joka on $G$ ; katso rivi .
etiketti: 1. Kaavion kärkeen tai reunaan liittyvät tiedot. Merkitty kuvaaja on kuvaaja, jonka kärjissä tai reunoissa on tarroja. Termeillä kärkipiste- tai reunamerkittyjä voidaan käyttää määrittämään, millä kaavion kohteilla on tunnisteet. Kaavioiden merkinnät viittaavat useisiin eri ongelmiin, jotka liittyvät tarrojen määrittämiseen kaavioihin tietyin rajoituksin. Katso myös kaavion väritys , jossa tarrat tulkitaan väreiksi.; 2. Graafin laskennan yhteydessä kuvaajan kärkipisteiden sanotaan olevan merkittyjä, jos ne kaikki ovat erotettavissa toisistaan. Tämä voidaan tehdä esimerkiksi todeksi vahvistamalla kahdenvälinen vastaavuus pisteiden ja kokonaislukujen välillä 1: stä kaavion järjestykseen. Kun kärkipisteet on merkitty, toisilleen isomorfiset (mutta eri pistejärjestykset) kuvaajat lasketaan erillisiksi objekteiksi. Sitä vastoin, kun kärkipisteet ovat merkitsemättömiä, toisiinsa isomorfisia kuvaajaa ei lasketa erikseen.
puun lehti: 1. Lehtikärki tai riippuva kärki (erityisesti puussa) on kärki, jonka aste on $1$ . Lehtien reuna tai riipusreuna on reuna, joka yhdistää lehtikärjen sen yksittäiseen naapuriin.; 2. lehtiä teho puun on kuvaaja jonka kärjet ovat puun lehdet ja jonka reunat connect lehtiä joiden etäisyys puussa on korkeintaan tietyn kynnyksen.
pituus: Painotamattomassa kaaviossa pyörän, polun tai kävelyn pituus on sen käyttämien reunojen määrä. Painotetussa kaaviossa se voi sen sijaan olla sen käyttämien reunojen painojen summa. Pituus on käytetään määrittelemään lyhimmän polun , ympärysmitta (lyhin syklin pituus), ja pisin polku välillä kaksi pistettä kuvaajan.
taso: 1. Tämä on solmun syvyys plus 1, vaikka jotkut määrittävät sen sen sijaan olevan syvyyden synonyymi . Solmun taso juurtuneessa puussa on solmujen lukumäärä reitillä juuresta solmuun. Esimerkiksi juurilla on taso 1 ja missä tahansa sen vierekkäisistä solmuista taso 2.; 2. Joukko kaikkia solmuja, joilla on sama taso tai syvyys.
linja: Suunnatun reunan synonyymi. Viivadiagrammi, $L (G)$ on kuvaaja, $G$ on graafinen esitys, jonka huippukulma kunkin reunan $G$ ja reunan kunkin parin reunoja, jotka jakavat päätepiste $G$ .
kytkentä: Synonyymi rappeutumiselle .
lista: 1. Viereisyysluettelo on graafinen kuvaajaalgoritmeissa käytettävä kaavioiden tietokoneesitys.; 2. Luetteloväritys on kuvaajan värityksen muunnelma, jossa jokaisella kärjellä on luettelo käytettävissä olevista väreistä.
paikallinen: Kaavion paikallinen ominaisuus on ominaisuus, jonka määräävät vain kaavion kärkipisteiden naapurustot . Esimerkiksi kuvaaja on paikallisesti äärellinen, jos kaikki sen naapurustot ovat äärellisiä.
silmukka: Silmukka tai itse silmukka on reuna jonka molemmat päätepisteet ovat samat kärki. Se muodostaa syklin, jonka pituus on $1$ . Nämä eivät ole sallittuja yksinkertaisissa kaavioissa.

M

suurennus: Synonyymi kärkien laajentumiselle .
vastaavat: Sovitus on joukko reunoja jossa ei ole kahta osuutta mitään kärki. Piste on sovitettu tai kylläinen, jos se on yksi sovituksen reunan päätepisteistä. Täysin vastaa tai täydellinen sovitus on vastaava, joka vastaa joka kärkeen; sitä voidaan kutsua myös 1-tekijäksi, ja se voi olla olemassa vain silloin, kun järjestys on parillinen. Lähes täydellinen täsmäytys parittomassa järjestyksessä olevassa kaaviossa on sellainen, joka kyllästää kaikki paitsi yhden kärkipisteen. Enintään sovitus on vastaava, joka käyttää niin paljon reunoja kuin mahdollista; kaavion $G$ täsmäytysluku $α' (G)$ on enimmäissovituksen reunojen määrä. Suurin sovitus on täsmäys, johon ei voi lisätä muita reunoja.
maksimi: 1. Tietyn kuvaajan $G$ osakaavio on tietylle ominaisuudelle maksimaalinen, jos sillä on kyseinen ominaisuus, mutta millään muulla sen supergrafilla, joka on myös $G:$ n osakuvaaja, ei ole samaa ominaisuutta. Toisin sanoen se on ominaisuuden alikuvien maksimielementti . Esimerkiksi maksimi -klikki on täydellinen osakaavio, jota ei voi laajentaa suuremmaksi täydelliseksi alikuvaajaksi. Sana "maksimi" tulisi erottaa "maksimista": suurin osakaavio on aina maksimaalinen, mutta ei välttämättä päinvastoin.; 2. Yksinkertainen kuvaaja, jolla on tietty ominaisuus, on tälle ominaisuudelle maksimaalinen, jos siihen ei ole mahdollista lisätä muita reunoja (pitäen kärkipisteitä muuttumattomina) säilyttäen samalla kuvaajan yksinkertaisuuden ja ominaisuuden. Siten esimerkiksi maksimaalinen tasomainen kuvaaja on tasomainen kuvaaja siten, että jos siihen lisätään lisää reunoja, syntyy ei-tasomainen kuvaaja.
enimmäismäärä: Tietyn kaavion $G$ osakaavio on maksimi tietylle ominaisuudelle, jos se on suurin alikaavio (järjestyksen tai koon mukaan) kaikista kyseisen ominaisuuden alikuvauksista. Esimerkiksi maksimiklikki on mikä tahansa tietyn kaavion suurimmista klikkeista.
mediaani: 1. Pistekolmikon mediaani, piste, joka kuuluu lyhyimpiin polkuihin kaikkien kärkiparien välillä, erityisesti mediaani- ja modulaarikaavioissa .; 2. Mediaanikuvaaja on kuvaaja, jossa jokaisella kolmella pisteellä on yksilöllinen mediaani.
Meyniel: 1. Henri Meyniel, ranskalainen graafiteoreetikko.; 2. Meyniel -kuvaaja on kuvaaja, jossa jokaisessa parittomassa jaksossa, jonka pituus on vähintään viisi, on vähintään kaksi sointua.
minimaalinen: Tietyn ominaisuuden osakaavio on minimaalinen tietylle ominaisuudelle, jos sillä on kyseinen ominaisuus, mutta millään sen asianmukaisella osakaavalla ei ole samaa ominaisuutta. Toisin sanoen se on ominaisuuden alikuvien minimaalinen osa .
pienin leikkaus: Leikkaus , jonka cut-sarja on vähintään kokonaispainosta, mahdollisesti rajoittaa leikkauksia, jotka erottavat nimetty kärkipisteparin; niille on tunnusomaista max-flow min-cut -lause .
alaikäinen: Kaavio $H$ on toisen graafin $G$ sivuaine , jos $H$ voidaan saada poistamalla reunat tai kärjet $G: stä$ ja supistamalla reunat $G: ssä$ . Se on matala molli, jos se voidaan muodostaa sivuaineeksi siten, että $G:$ n osakaavioilla, jotka on supistettu muodostamaan $H$ -pisteitä, on kaikki halkaisijaltaan pieniä. $H$ on topologinen vähäinen ja $G$ , jos $G$ on aligraafi, joka on osa-alue on $H$ . Graafi on $H$ -minor vapaana, jos se ei ole $H$ vähäisenä. Kaavioiden perhe on vähäisesti suljettu, jos se on suljettu alaikäisten alaisuudessa; Robertson-Seymour lause ominaista vähäinen suljettu perheiden, joilla on rajallinen joukko kielletty alaikäisten.
sekoitettu: Sekoitettu kaavio on graafinen esitys, joka voi sisältää sekä suunnattu ja suuntaamaton reunat.
modulaarinen: 1. Modulaarinen kuvaaja , kuvaaja, jossa jokaisella kärkipisteellä on vähintään yksi keskipiste, joka kuuluu lyhyimpiin polkuihin kolminkertaisten parien välillä.; 2. Modulaarinen hajoaminen , kuvaajan hajottaminen osakaavioiksi, joiden sisällä kaikki kärkipisteet yhdistyvät muuhun kuvaajaan samalla tavalla.; 3. Kaavion ryhmittymisen modulaarisuus , klusterien välisten reunojen määrän ero odotetusta arvosta.
yksitoikkoinen: Kaavioiden yksitoikkoinen ominaisuus on ominaisuus, joka on suljettu osakaavioiden alla: jos $G:$ llä on perinnöllinen ominaisuus, niin sen on oltava myös jokaisessa $G: n$ osakaaviossa . Vertaa perinnöllistä (suljettu indusoitujen alakuvien alla) tai vähäisesti suljettua (suljettu alaikäisten alla).
Mooren kaavio: Moore kuvaaja on säännöllinen graafi, jolle Moore sidottu täyttyy tarkasti. Moore -raja on Edward F.Mooren osoittama kaavion asteen, halkaisijan ja järjestyksen eriarvoisuus . Jokainen Moore -kuvaaja on häkki.
monikuvaaja: Multigraph on kuvaaja, joka mahdollistaa useiden adjacencies (ja, usein, itse-silmukat); kaavio, jonka ei tarvitse olla yksinkertainen.
moninkertainen vierekkäisyys: Moninkertainen vierekkäisyys tai usea reuna on joukko useampaa kuin yhtä reunaa, joilla kaikilla on samat päätepisteet (samaan suuntaan, kun kyseessä on suunnattu kuvaaja). Kaaviota, jossa on useita reunoja, kutsutaan usein monikuvaajaksi.
moninaisuus: Reunan moninaisuus on usean vierekkäisyyden reunojen määrä. Kaavion moninaisuus on minkä tahansa sen reunan enimmäismäärä.

N

N: 1. Katso merkinnät avoimista ja suljetuista lähiöistä kohdasta naapurusto .; 2. Pieniä kirjaimia $n$ käytetään usein (erityisesti tietotekniikassa) osoittamaan pisteiden lukumäärää tietyssä kaaviossa.
naapuri-
naapuri: Piste, joka on tietyn kärjen vieressä.
naapurustossa
naapurustossa: Avoin -osassa (tai -osassa) on piste $v$ on aligraafi indusoima kaikki pisteet, jotka ovat lähellä $vastaan$ . Suljettu naapuruus määritellään samalla tavalla, mutta sisältää myös $v: n$ itse. Avoin naapurustossa $v$ on $G$ voidaan merkitä $N G (v)$ tai $N (v)$ , ja suljetun naapuruston voidaan merkitä $N G [v]$ tai $N [v]$ . Kun naapuruston avoimuutta tai sulkeutumista ei ole määritelty, sen oletetaan olevan avoin.
verkkoon: Kaavio, jossa solmuihin ja/tai reunoihin liittyy attribuutteja (esim. Nimiä).
solmu: Synonyymi vertexille .
ei-reuna: Ei-reuna tai reunan vastainen on pari kärkipisteitä, jotka eivät ole vierekkäin; täydennyskaavion reunat.
nollakaavio: Katso tyhjä kaavio .

O

outo: 1. Pariton sykli on sykli, jonka pituus on pariton. Pariton ympärysmitta ei-kaksijakoinen kuvaaja on pituus sen lyhin pariton aikana. Pariton reikä on parittoman syklin erityistapaus: yksi, joka on indusoitu ja jossa on neljä tai useampia kärkipisteitä.; 2. Pariton kärki on piste, jonka aste on pariton. Jonka kättely lemman joka äärellinen suuntaamattoman graafin on parillinen määrä pariton pisteiden.; 3. Pariton korva on yksinkertainen polku tai yksinkertainen sykli, jossa on pariton määrä reunoja, ja sitä käytetään tekijäkriittisten kaavioiden parittomissa korvakuvissa; nähdä korva .; 4. Pariton sointu on reuna, joka yhdistää kaksi kärkeä, jotka ovat parittoman syklin päässä parittoman matkan päässä toisistaan. Parittomia sointuja käytetään vahvasti sointukäyrien määrittämiseen .; 5. pariton kuvaaja on erikoistapaus Kneser kaavio , jossa on yksi kärkipiste kunkin $(n - 1)$ -elementti osajoukko $(2 n - 1)$ -elementti sarja, ja reuna, joka yhdistää kaksi osajoukkoa, kun niiden vastaavat joukot ovat hajottaa.
avata: 1. Katso naapurusto .; 2. Katso kävely .
Tilaus: 1. Kaavion $G$ järjestys on sen pisteiden lukumäärä $| | V (G) |$ . Muuttujaa $n$ käytetään usein tähän määrään. Katso myös koko , reunojen määrä.; 2. Kaavioiden logiikan tyyppi ; katso ensimmäinen ja toinen tilaus .; 3. Graafin järjestys tai järjestys on sen kärkipisteiden järjestely sekvenssiksi, erityisesti topologisen järjestyksen yhteydessä (suunnatun asyklisen kuvaajan järjestys, jossa jokainen reuna siirtyy aikaisemmasta kärjestä myöhempään kärkeen järjestyksessä ) ja rappeutumisjärjestys (järjestys, jossa jokaisella kärjellä on vähimmäisaste sen ja kaikkien myöhempien kärkipisteiden indusoidussa osakaaviossa).; 4. Katso sataman tai brammlen järjestys kohdasta haven ja Bramble .
suuntautuminen
suuntautunut: 1. suunta on suuntaamattoman graafin on osoituksen suuntiin sen reunat, joten se tulee suunnattu graafi. Suunnattu kuvaaja on kuvaaja, jolle on annettu suunta. Joten esimerkiksi polytree on suuntautunut puu; se eroaa suunnatusta puusta (arborescence) siinä, että sen reunojen suuntiin ei vaadita johdonmukaisuutta. Muita erityisiä suuntautumistyyppejä ovat turnaukset , täydellisten kaavioiden suunnat; vahvat suuntaukset , vahvasti toisiinsa liittyvät suuntaukset; asykliset suuntaukset , asykliset suuntaukset ; Eulerian suuntaukset , Eulerian suuntaukset ; ja transitiiviset suuntaukset , suuntaukset, jotka ovat väliaikaisesti suljettuja.; 2. Suunniteltu kuvaaja, jota jotkut kirjoittajat käyttävät suunnatun kuvaajan synonyyminä .
ulos-aste: Katso tutkinto .
ulompi: Katso kasvot .
ulompi tasomainen: Outerplanar kaavio on graafinen esitys, joka voidaan upottaa tasossa (ilman risteykset) siten, että kaikki pisteet ovat ulkopinnalle kuvaaja.

P

polku: Polku voi olla joko kävellä tai kävellä ilman toistuva pisteet ja siten reunat (kutsutaan myös yksinkertainen polku), lähteestä riippuen. Tärkeitä erityistapauksia ovat indusoidut polut ja lyhyimmät reitit .
polun hajoaminen: Polku hajoaminen graafin $G$ on puu hajoaminen, jonka taustalla puu on polku. Sen leveys määritellään samalla tavalla kuin puiden hajoamiselle, yksi pienempi kuin suurimman pussin koko. Pienin leveys mitä tahansa reittiä hajoamisen $G$ on pathwidth ja $G$ .
reitin leveys: Pathwidth graafin $G$ on pienin leveys polku hajoamisen $G$ . Se voidaan määritellä myös $G:$ n intervallin täyttymisen napsautussumman perusteella . Se on aina kaistanleveyden ja $G:$ n puuleveyden välissä . Se tunnetaan myös nimellä välipaksuus, pisteiden erotusnumero tai solmun etsintänumero.
riipus: Katso lehti .
täydellinen: 1. Täydellinen kuvaaja on kuvaaja, jossa jokaisessa indusoidussa osakaaviossa kromaattinen luku on yhtä suuri kuin klikki. Täydellinen kaavio lause ja vahva täydellinen kaavio lause on kaksi lauseet noin täydellinen kaavioita, entinen osoittautumassa että niiden komplementit ovat myös täydellinen ja jälkimmäinen osoittautumassa, että ne ovat täsmälleen kuvaajat, joilla ei ole pariton reikiä tai anti-reikiä.; 2. Täysin tilattava kuvaaja on kuvaaja, jonka kärkipisteet voidaan järjestää siten, että ahne väritysalgoritmi tällä järjestyksellä värjää optimaalisesti jokaisen indusoidun alikuvaajan. Täysin tilattavat kuvaajat ovat täydellisten kaavioiden alaluokka.; 3. Täydellinen vastaavuus on sovitus, joka kyllästää jokaisen kärjen; katso vastaavaa .; 4. Täydellinen 1-kerroin on osio kaavion reunoista täydellisiksi täsmäytyksiksi siten, että molemmat vastaavuudet muodostavat Hamiltonin syklin.
oheislaite: 1. Perifeerinen sykli tai erottamaton sykli on sykli, jossa on enintään yksi silta.; 2. Perifeerinen kärki on huippu, jonka epäkeskisyys on suurin. Puussa tämän on oltava lehti.
Petersen: 1. Julius Petersen (1839–1910), tanskalainen graafiteoreetikko.; 2. Petersen-kuvaaja , 10-pisteinen 15-reunainen kuvaaja, jota käytetään usein vastaesimerkinä.; 3. Petersenin lause, jonka mukaan jokainen sillaton kuutiokäyrä vastaa täydellisesti toisiaan.
tasomainen: Tasomainen kaavio on graafinen esitys, joka on upotus päälle euklidisessa tasossa. Tasokuvaaja on tasokuvaaja, jolle tietty upotus on jo korjattu. $K$ -planar kuvaaja on sellainen, joka voidaan tehdä tasossa kanssa korkeintaan $k$ risteykset per reuna.
polytree: Polytree on suuntautunut puu; vastaavasti suunnattu asyklinen kuvaaja, jonka ohjaamaton kuvaaja on puu.
tehoa: 1. kaavio voima $G k$ graafin $G$ on toinen kuvaaja samalla kärki asettaa; kaksi pistettä ovat vierekkäiset $G k$ , kun ne ovat etäisyydellä korkeintaan $k$ on $G$ . Lehtiä teho on läheistä sukua käsite, joka on peräisin teho puun ottamalla aligraafia aiheuttama puun lehtiä.; 2. Virta kaavio analyysi on menetelmä analysoimiseksi monimutkaisten verkkojen tunnistamalla klikkien, bicliques, ja tähdet verkoston sisällä.; 3. Virta lait , että asteen jakaumat on mittakaavasta verkot ovat ilmiötä, jossa solmujen lukumäärä tietyn aste on verrannollinen voima astetta.
edeltäjä: Kärki tulossa ennen tiettyä kärki on suunnattu polku .
asianmukainen: 1. Oikea alikuvaaja on osakaavio, joka poistaa ainakin yhden kärjen tai reunan suhteessa koko kuvaajaan; äärellisille kaavioille oikeat osakaaviot eivät ole koskaan isomorfisia koko kuvaajalle, mutta äärettömille kaavioille ne voivat olla.; 2. Oikea väritys on värien osoittaminen kaavion kärkipisteisiin (väritys), joka määrittää eri värit kunkin reunan päätepisteisiin; katso väri .; 3. Oikea aikaväligraafi tai oikea ympyräkaarigrafiikka on leikkauskaavio, joka koostuu intervallien tai ympyräkaarien (vastaavasti) kokoelmasta siten, että mikään väli tai kaari ei sisällä toista aikaväliä tai kaarta. Oikeita aikaväleitä kutsutaan myös yksikköintervallikaavioiksi (koska ne voidaan aina esittää yksikkövälillä) tai välinpitämättömyyskaavioiksi.
omaisuutta: Kuvaaja ominaisuus on jotain, joka voi olla totta joidenkin kaavioita ja vääriä toisten ja että riippuu vain kuvaajan rakenteeseen eikä satunnaisia tietoja kuten tarroja. Kuvaajan ominaisuuksia voidaan vastaavasti kuvata kuvaajaluokittain (kuvaajat, joilla on tietty ominaisuus). Yleisemmin kuvaajan ominaisuus voi olla myös kuvaajafunktio, joka on jälleen riippumaton satunnaisista tiedoista, kuten kaavion koosta, järjestyksestä tai asteesta; tätä yleisempää ominaisuuden määritelmää kutsutaan myös kuvaajan invariantiksi.
pseudoforest: Pseudoforest on suuntaamattoman graafin, jossa jokainen kytketty laite on korkeintaan yksi sykli, tai suunnattu graafi, jossa jokainen piste on korkeintaan yksi lähtevä reuna.
pseudografia: Pseudografi on kuvaaja tai monikuva, joka sallii itsesilmukoinnin.

Q

lähes viivakaavio: Kvasiviivainen kuvaaja tai paikallisesti kaksipartiittinen kuvaaja on kuvaaja, jossa jokaisen kärjen avoin naapuruus voidaan jakaa kahteen klikkiin. Nämä kaaviot ovat aina kynsittömiä, ja ne sisältävät erikoistapauksena viivakaavioita . Niitä käytetään kynsittömien kaavioiden rakenneteoriassa.
vapina: Vapista on suunnattu multigraph, sellaisena kuin sitä käytetään luokkaan teoriassa . Värin reunoja kutsutaan nuoliksi.

R

säde: Kaavion säde on minkä tahansa kärjen pienin epäkeskisyys .
Ramanujan: Ramanujan kaavio on kaavio, jonka spektrin laajeneminen on niin suuri kuin mahdollista. Toisin sanoen se on $d$ -säännöllinen kuvaaja, niin että sen vierekkäismatriisin toiseksi suurin ominaisarvo on korkeintaan . ${\ displaystyle 2 {\ sqrt {d-1}}}$
säde: Säde äärettömässä kaaviossa on ääretön yksinkertainen polku, jolla on täsmälleen yksi päätepiste. Päät kuvaajan ovat ekvivalenssiluokkia säteitä.
tavoitettavuus: Kyky päästä yhdestä kärjestä toiseen kuvaajan sisällä .
tavoitettavissa: On myönteinen saavutettavuus . Kärki $y$ sanotaan olevan saavutettavissa kärkipiste $x$ jos on olemassa polku välillä $x$ ja $y$ .
tunnistettavissa: Yhteydessä on rekonstruktio arveluihin , kuvaaja, joka ominaisuus on tunnistettavissa, jos sen totuus voidaan määrittää kannen kuvaaja. Monien kuvaajan ominaisuuksien tiedetään olevan tunnistettavissa. Jos rekonstruktio -olettamus on tosi, kaikki kuvaajan ominaisuudet ovat tunnistettavissa.
jälleenrakentaminen: Rekonstruktio arveluihin todetaan, että kukin suuntaamattoman graafin $G$ on määritelty yksilöllisesti sen kannelle , monotoimisarjan kaavioita muodostetaan poistamalla yksi kärki päässä $G$ kaikilla mahdollisilla tavoilla. Tässä yhteydessä jälleenrakennus on kaavion muodostaminen sen kannelta.
suorakulmio: Yksinkertainen sykli, joka koostuu täsmälleen neljästä reunasta ja neljästä kärjestä.
säännöllinen: Kaavio on $d$ -säännöllinen, kun sen kaikkien kärkien aste on $d$ . Säännöllinen graafi on kuvaaja, joka on $vrk$ -regular joillekin $d$ .
säännöllinen turnaus: Säännöllinen turnaus on turnaus, jossa aste on yhtä korkea kuin aste kaikissa pisteissä.
käänteinen: Katso transponointi .
juuri: 1. Nimetty kärki käyrässä, erityisesti suunnatuissa puissa ja juurtuneissa kaavioissa .; 2. Käänteisoperaatio kuvaajan teholle : kaavion $G$ $k$ -juuri on toinen saman kärkipisteen kuvaaja siten, että kaksi pistettä ovat vierekkäin $G: ssä$ silloin ja vain, jos niiden etäisyys on korkeintaan $k$ juurissa.

S

toinen tilaus: Graafien toisen kertalogiikan logiikka on eräänlainen logiikka, jossa muuttujat voivat edustaa pisteitä, reunoja, kärkipisteitä ja (joskus) reunajoukkoja. Tämä logiikka sisältää predikaatteja, joilla testataan, onko piste ja reuna satunnaisia, sekä kuuluuko kärki tai reuna joukkoon. Erotetaan ensimmäisen asteen logiikasta, jossa muuttujat voivat edustaa vain huippuja.
kyllästynyt: Katso vastaavuutta .
haettava numero: Solmuhaun numero on synonyymi polun leveydelle .
itsesilmukka: Synonyymi silmukalle .
erottava kärki: Katso artikulaatiokohta .
erotusnumero: Vertex -erotusnumero on synonyymi polun leveydelle .
yksinkertainen: 1. Yksinkertainen kuvaaja on kuvaaja ilman silmukoita ja ilman useita vierekkäisyyksiä. Toisin sanoen jokainen reuna yhdistää kaksi erillistä päätepistettä eikä kahdella reunalla ole samoja päätepisteitä. Yksinkertainen reuna on reuna, joka ei ole osa moninkertaista vierekkäisyyttä. Monissa tapauksissa kaavioiden oletetaan olevan yksinkertaisia, ellei toisin mainita.; 2. Yksinkertainen polku tai yksinkertainen sykli on polku tai sykli, jolla ei ole toistuvia pisteitä eikä siten toistuvia reunoja.
pesuallas: Suunnattuun kuvaajaan sijoitettu pesuallas on kärki, jossa ei ole lähteviä reunoja (ulos-aste on 0).
koko: Kaavion $G$ koko on sen reunojen lukumäärä, $| E (G) |$ . Muuttujaa $m$ käytetään usein tähän määrään. Katso myös kärkipisteiden järjestys .
pienen maailman verkko: Pieni-maailma verkko on kuvaaja, jossa useimmat solmut eivät ole naapureita keskenään, mutta useimmat solmut pääsee kaikkiin muihin solmussa pieni määrä humalaa tai vaiheita. Erityisesti pienen maailman verkko määritellään kuvaajaksi, jossa tyypillinen etäisyys L kahden satunnaisesti valitun solmun välillä (tarvittavien vaiheiden määrä) kasvaa suhteessa verkon solmujen N logaritmiin
haukkua: Snark on yksinkertainen, on kytketty portaattomasti kuutio kuvaajan kromaattinen indeksi on 4.
lähde: Lähde suunnatussa kaaviossa on kärki, jossa ei ole tulevia reunoja (aste on 0).
tilaa: In algebrallinen graafiteoria , useita vektoriavaruudet yli binaarikenttään voi liittyä graafinen esitys. Jokaisella on vektoriensa reunoja tai kärkipisteitä ja joukkojen symmetrinen ero sen vektorisummaoperaationa. Reuna tila on tila kaikkien sarjaa reunat, ja Vertex avaruus on tilaa kaikille sarjaa kärjet. Leikkaus tila on aliavaruus reunan tilaa, joka on leikattu sarjaa kaaviossa sen osia. Sykli tila on Eulerin virittävä subgraphs sen osia.
jakoavain: Jakoavain on (yleensä harva) kuvaaja, jonka lyhyimmät polut vastaavat tiheän kuvaajan tai muun metrisen tilan matkoja. Muunnelmia ovat geometriset jakoavaimet , kuvaajat, joiden kärkipisteet ovat pisteitä geometrisessa avaruudessa; puun jakoavaimet , kaavion puita, joiden etäisyydet vastaavat kuvaajan etäisyyksiä, ja kuvaajan jakoavaimet, tiheän kuvaajan harvat osakaaviot, joiden etäisyydet vastaavat alkuperäisen kuvaajan etäisyyksiä. Ahne jakoavain on ahneella algoritmilla rakennettu kaavionavain, yleensä sellainen, joka ottaa huomioon kaikki reunat lyhyimmästä pisimpään ja pitää ne, jotka ovat tarpeen etäisyyden lähentämisen säilyttämiseksi.
ulottuu: Alakuvaaja ulottuu, kun se sisältää kaikki annetun kuvaajan kärkipisteet. Tärkeitä tapauksia ovat puiden ulottuvuus, puiden alakaaviot ja täydelliset täsmäytykset , jotka kattavat osakaaviot. Kattavaa osakaaviota voidaan kutsua myös tekijäksi , varsinkin (mutta ei vain) silloin, kun se on säännöllinen.
harva: Harva kaavio on yksi, joka on muutaman reunat suhteessa sen solmujen lukumäärä. Joissakin määritelmissä saman ominaisuuden pitäisi olla totta myös kaikille annetun kaavion osakaavioille.
spektrinen
spektri: Spektri on kuvaaja kokoelma ominaisarvot sen vierusmatriisin. Spektraalikuvaajateoria on kuvaajateorian haara, joka käyttää spektrejä kaavioiden analysointiin. Katso myös spektrin laajeneminen .
jakaa: 1. Jaettu kuvaaja on kuvaaja, jonka kärkipisteet voidaan osittaa klikiksi ja itsenäiseksi joukkoksi. Siihen liittyvää kuvaajaluokkaa, kaksoisjakokaavioita, käytetään vahvan täydellisen kuvaajan lauseen todistamiseen.; 2. jaettu mielivaltaisen kuvaaja on osio sen kärkipisteet kahteen ei-tyhjä subsets, siten, että reunat, jotka ulottuivat tämän perus- muodostavat täydellisen kaksiosainen aligraafi. Kaavion halkeamia voidaan esittää puurakenteella, jota kutsutaan sen hajoamishajoamiseksi . Jakaumaa kutsutaan vahvaksi halkeamaksi, kun sitä ei ylitä mikään muu jako. Jakoa kutsutaan ei -triviaaliksi, kun sen molemmilla puolilla on enemmän kuin yksi kärki. Kaaviota kutsutaan primeksi, kun sillä ei ole ei -triviaalisia jakoja.
neliö-: 1. Kaavion $G$ neliö on kuvaajan teho $G 2$ ; toiseen suuntaan, $G$ on neliöjuuri $G 2$ . Puoli-neliö kaksiosaisen graafin kaaviota on aligraafi sen neliön indusoiman toisella puolella bipartition.; 2. Neliökuvaaja on tasomainen kuvaaja, joka voidaan piirtää siten, että kaikki rajoitetut pinnat ovat 4-syklisiä ja kaikki pisteet, joiden aste on ≤ 3, kuuluvat ulkopintaan.; 3. neliö verkkoon kuvaaja on ristikko kaavio määritelty peräisin olevia tasossa, jossa kokonaisluku koordinaatit yhdistetty yksikön pituus reunat.
vakaa: Vakaa joukko on itsenäisen joukon synonyymi .
tähti: Tähti on puu yhden sisäisen kärki; Vastaavasti se on täydellinen kahden osapuolen kuvaaja $K 1, n$ joillekin $n \geq 2$ . Kolmen lehden tähden erityistapausta kutsutaan kynsiksi.
vahvuus: Vahvuus kuvaaja, on vähintään suhde reunojen määrä poistetaan kaavion komponentit on luotu, kaikkien mahdollista poistamista; se on analoginen sitkeydelle, joka perustuu kärkipisteiden poistoihin.
vahva: 1. Katso vahvat yhteydet ja vahvasti kytkettyjen suunnattujen kaavioiden komponentit kohdasta Yhdistetty ja komponentti . Vahva suunta on suunta, joka on vahvasti kytketty; katso suunta .; 2. Katso vahvan täydellisen kuvaajan lause , katso täydellinen .; 3. Vahvasti säännöllinen kuvaaja on säännöllinen kuvaaja, jossa jokaisella kahdella vierekkäisellä kärjellä on sama määrä jaettuja naapureita ja jokaisella kahdella vierekkäisellä kärjellä on sama määrä jaettuja naapureita.; 4. Voimakkaasti sointukuvaaja on sointokuvio, jossa jokaisella kuuden tai useamman parillisella jaksolla on pariton sointu.; 5. Vahvasti täydellinen kuvaaja on kuvaaja, jossa jokaisella indusoidulla alikuvaajalla on itsenäinen joukko, joka täyttää kaikki maksimiklikit. Meyniel kuvaajat kutsutaan myös "vahvasti täydellinen kaavioita", koska niissä, joka kärkeen kuuluu tällainen riippumaton asetettu.
alimetsä: Alakuvaaja metsästä .
alakuvaaja: Aligraafi kuvaajan $G$ on toinen kaavio joka on muodostettu osajoukko pisteiden ja reunojen $G$ . Vertex -osajoukon on sisällettävä kaikki reuna -osajoukon päätepisteet, mutta se voi sisältää myös muita kärkipisteitä. Kattava osakaavio on kaavion kaikki kärkipisteet; indusoitu osakaavio on sellainen, joka sisältää kaikki reunat, joiden päätepisteet kuuluvat kärkipisteiden osajoukkoon.
alipuuta: Osapuu on puun liitetty osakaavio. Joskus juurtuneille puille alipuut määritellään erityyppisiksi yhdistetyiksi osakaavioiksi, jotka muodostavat kaikki valitusta kärjestä saavutettavat kärjet ja reunat.
seuraaja: Kärki , jotka sen jälkeen, kun tietyn kärki on suunnattu polku .
ylikonsentraattori: Superconcentrator on graafinen esitys, jossa on kaksi nimetty ja samankokoista osajoukkoja pisteiden $I$ ja $O$ , siten, että jokaista kahta samankokoista osajoukkojen $S$ ja $I$ ja $T$ $O$ on olemassa perheen erillisiä polkuja yhdistää jokaisen kärjen $S$ on kärjen $T$ . Joidenkin lähteiden lisäksi vaatia, että superconcentrator olla suunnattu asyklinen kaavio, jossa $olen$ sen lähteet ja $O$ sen nieluja.
superkuvaaja: Kaavio, joka on muodostettu lisäämällä pisteitä, reunoja tai molempia kuvaajaan. Jos $H$ on $G:$ n osakaavio , niin $G$ on $H:$ n superkuvaaja .

T

teeta: 1. Teetagrammi on kolmen sisäisesti hajoavan (yksinkertaisen) polun liitto, joilla on samat kaksi erillistä päätepistettä.; 2. theta kuvaaja kokoelma kohtia euklidisen on konstruoitu rakentamalla järjestelmä, kartioita, jotka ympäröivät kutakin kohta ja lisäämällä yksi reuna kohti kartio, siihen pisteeseen, jonka projisointi keskeinen säde kartion on pienin.; 3. Kaavion Lovász -luku tai Lovász -teeta -funktio on graafinen invariantti, joka liittyy klikin numeroon ja kromaattiseen lukuun ja joka voidaan laskea polynomi -ajassa semidefinite -ohjelmoinnilla.
topologinen: 1. Topologinen kuvaaja on kuvaajan kärkien ja reunojen esitys tason pisteiden ja käyrien mukaan (ei välttämättä välttämättä risteyksiä).; 2. Topologinen kuvaajateoria on graafisten upotusten tutkimus.; 3. Topologinen lajittelu on algoritminen ongelma järjestettäessä suunnattu asyklinen kuvaaja topologiseen järjestykseen, pistejärjestykseen siten, että jokainen reuna kulkee sekvenssin aikaisemmasta kärjestä myöhemmäksi.
irrotettu kokonaan: Synonyymi reunattomalle .
kiertue: Suljettu polku, kävely, joka alkaa ja päättyy samasta kärjestä ja jolla ei ole toistuvia reunoja. Euler -kiertueet ovat matkoja, jotka käyttävät kaikkia kuvaajan reunoja; katso Eulerian .
turnaus: Turnauksen on suunta täydellisen kaavio; toisin sanoen se on suunnattu kuvaaja siten, että jokainen kaksi kärkeä on yhdistetty täsmälleen yhdellä suunnatulla reunalla (kulkee vain yhdessä kahdesta suunnasta kahden kärjen välillä).
jäljitettävissä: Jäljitettävissä kaavio on graafinen esitys, joka sisältää Hamiltonin polku.
polku: Kävellä ilman toistuvaa reunoja.
transitiivinen: Se liittyy transitiiviseen ominaisuuteen . Transitiivinen sulkeminen tietyn suunnattu kuvio on kuvaaja samalla kärki joukko, joka on reuna yhdestä kärki toiseen aina, kun alkuperäinen kuvaaja on polku, joka yhdistää saman kaksi pistettä. Transitiivinen vähentäminen kuvaajan on minimaalinen graafin, jolla on sama transitiivisen sulkeminen; suunnatuissa asykli -kaavioissa on ainutlaatuinen transitiivinen vähennys. Transitiivinen suunta on suunta kaaviosta, joka on sen oma transitiivista sulkeminen; se on olemassa vain vertailukelpoisia kaavioita varten .
saattaa osaksi kansallista lainsäädäntöä: Transpoosi kaavio tietyn suunnattu kuvio on kuvaaja samalla pisteiden, jossa kunkin reunan suunnassa käännettyjä. Sitä voidaan kutsua myös kaavion käänteiseksi tai käänteiseksi.
puu: 1. Puu on suunnattu kuvaaja, joka on sekä yhdistetty että asyklinen, tai suunnattu kuvaaja, jossa on ainutlaatuinen kävely yhdestä kärjestä (puun juuri) kaikkiin jäljellä oleviin kärkiin.; 2. $K$ -puu on kuvaaja, joka muodostuu liimaamalla $(k + 1)$ -klikkejä yhteen jaetuissa $k$ -klikeissä. Puu tavallisessa mielessä on tämän määritelmän mukaan $1$ -puu.
puiden hajoaminen: Puu hajoaminen graafin $G$ on puu, jonka solmut on merkitty sarjaa kärjet on $G$ ; näitä sarjoja kutsutaan pusseiksi. Jokaista kärkeä $v$ varten pussien, jotka sisältävät $v,$ on indusoitava puun osapuu, ja jokaiselle reunalle $uv$ on oltava pussi, joka sisältää sekä $u: n$ että $v: n$ . Puun hajoamisen leveys on yksi pienempi kuin minkä tahansa pussin pisteiden enimmäismäärä; treewidth ja $G$ on pienin leveys tahansa puun hajoamista $G$ .
puun leveys: Treewidth graafin $G$ on pienin leveys puun hajoamisen $G$ . Se voidaan myös määritellä, että klikki määrä on jännemäinen loppuun ja $G$ , suuruusluokkaa satama on $G$ , tai suuruusluokkaa karhunvatukka ja $G$ .
kolmio: Kolmen pituinen sykli kaaviossa. Kolmio vapaa kuvaaja on suuntaamaton verkko, jossa ei ole yhtään kolmiota subgraphs.
Turán: 1. Pál Turán; 2. Turán -kuvaaja on tasapainoinen täydellinen moniosainen kuvaaja.; 3. Turánin lause sanoo, että Turán-kuvaajalla on suurin sallittu määrä reunoja tietyn järjestyksen kaikkien klikkaamattomien graafien joukossa.; 4. Turánin tiilitehtaan ongelma vaatii vähimmäismäärän risteyksiä täydellisen kahden osapuolen kuvaajan piirustuksessa.

U

ohjaamaton: Suuntaamattoman graafin on graafinen esitys, jossa kahden päätepisteen kunkin reunan ei eroteta toisistaan. Katso myös ohjattu ja sekoitettu . On sekoitettu kaavio , suuntaamattoman reuna on jälleen sellainen, jossa päätepisteet eivät ole erotettavissa toisistaan.
yhtenäinen: Hypergrafi on $k$ -yhtenäinen, kun sen kaikilla reunoilla on $k$ päätepistettä, ja yhtenäinen, kun se on $k$ -yhtenäinen joillekin $k: lle$ . Esimerkiksi tavalliset kuvaajat ovat samat kuin $2$ -yhtenäiset hypergrafit.
universaali: 1. Universaali kuvaaja on kuvaaja, joka sisältää osakaaviona kaikki tietyn kuvaajaperheen kuvaajat tai kaikki tietyn kokoiset tai -järjestyksiset kuvaajat tietyssä kuvaajaperheessä.; 2. Universaali kärki (jota kutsutaan myös huipuksi tai hallitsevaksi kärkipisteeksi) on kärki, joka on kaavion jokaisen muun kärjen vieressä. Esimerkiksi pyöräkaavioilla ja niihin liittyvillä kynnyskaavioilla on aina universaali kärki.; 3. Kaavojen logiikassa kärkeä, joka on yleisesti kvantifioitu kaavassa, voidaan kutsua kyseisen kaavan universaalipisteeksi.
painottamaton kaavio: Kaavio , jonka kärkipisteet ja reuna s ei ole osoitettu paino s ; painotetun kaavion vastakohta .

V

V: Katso kärkipiste .
valenssi: Synonyymi tutkintoon .
kärki: Kärki (monikko kärkipisteet) on (yhdessä reunat) toinen perusyksiköitä, joista kuvaajat on rakennettu. Kaavioiden kärkipisteitä pidetään usein atomiobjekteina, joilla ei ole sisäistä rakennetta.
kärjen leikkaus
erottava sarja: Joukko pisteiden joiden poistaminen katkaisee kuvaaja . Yhden kärjen leikkausta kutsutaan nivelpisteeksi tai leikkauspisteeksi .
kärkipiste: Tietyn kuvaajan $G$ pisteiden joukko , jota joskus merkitään $V: llä (G)$ .
kärkipisteet: Katso kärki .
Vizing: 1. Vadim G. Vizing; 2. Vizingin lause, jonka mukaan kromaattinen indeksi on enintään yksi enemmän kuin maksimiaste.; 3. Vizingin olettamus graafisten karteesisten tuotteiden hallitsevasta määrästä.
äänenvoimakkuutta: Pistejoukon asteiden summa.

W

$W$: $W$ -kirjainta käytetään pyörägraafien ja tuulimyllykaavioiden merkinnöissä . Merkintä ei ole standardoitu.
Wagner: 1. Klaus Wagner; 2. Wagner-kuvaaja , kahdeksan kärjen Möbius-tikkaat.; 3. Wagnerin lause, joka kuvaa tasomaisia kaavioita heidän kiellettyjen alaikäistensä perusteella.; 4. Wagnerin lause, joka luonnehtii pieniä $K 5$ -kaavioita.
kävellä: Kävellä on äärellinen tai ääretön sekvenssi, ja reunat , jotka tulevat sekvenssin pisteiden . Kävelyjä kutsutaan joskus myös ketjuiksi . Kävely on avoin, jos sen ensimmäinen ja viimeinen kärki ovat erilaiset, ja suljettu, jos ne toistetaan.
heikosti kytketty: Suunnattu graafi kutsutaan heikosti yhdistetty, jos korvaa kaikki sen suunnattu reunat suuntaamaton reunat tuottaa kytketty (suuntaamattoman) kaavio.
paino: Numeerinen arvo, joka on määritetty tarraksi kaavion kärkeen tai reunaan. Osakaavion paino on kyseisen osakaavion pisteiden tai reunojen painojen summa.
painotettu kuvaaja: Kaavio , jonka kärkipisteet tai reuna s on osoitettu paino s ; Tarkemmin sanottuna kärkipainotetun kuvaajan kärjissä on painoja ja reunapainotetun kuvaajan reunoissa painoja.
hyvin värillinen: Hyvin värinen kuvaaja on kuvaaja, jonka kaikki ahneet väriaineita käyttää samaa värien määrä.
hyvin peitetty: Hyvin peittämä kaavio on graafinen esitys, jonka kaikki maksimaalinen toisistaan riippumatonta ovat samankokoisia.
pyörä: Pyörä kaavio on graafinen esitys, joka on muodostettu lisäämällä universaali kärki yksinkertainen sykli.
leveys: 1. Synonyymi rappeutumiselle .; 2. Katso muita kaavion invariantteja, jotka tunnetaan nimellä leveys, katso kaistanleveys , haaranleveys , napsautusleveys , polun leveys ja puunleveys .; 3. Puun hajoamisen tai polun hajoamisen leveys on yksi pienempi kuin yhden sen pussin enimmäiskoko, ja sitä voidaan käyttää puunleveyden ja polun leveyden määrittämiseen.; 4. Suunnatun asyklisen kuvaajan leveys on ketjunvastaisuuden suurin kardinaalisuus.
tuulimylly: Tuulimylly kaavio on liitto kokoelma klikkien, kaikki samaa suuruusluokkaa kuin toisiaan, yksi yhteinen kärki kuuluvat kaikki klikkien ja kaikki muut kärjet ja reunat erillisiä.

Languages

In other projects

Graafiteorian sanasto - Glossary of graph theory

Symbolit

A

B

C

D

E

F

G

H

Minä

K

L

M

N

O

P

Q

R

S

T

U

V

W

Katso myös

Viitteet