Ordliste med grafteori - Glossary of graph theory

Dette er en ordliste for grafteori . Grafteori er studiet av grafer , systemer av noder eller hjørner forbundet i par med linjer eller kanter .

Symboler

Firkantede parenteser []
G [ S ] er den induserte sub-graf av en graf G for topp-punkt delsett S .
Prime symbol '
Den merkesymbol blir ofte brukt til å modifisere notasjon for graf invariantene slik at den gjelder for linjegraf i stedet for den gitte grafen. For eksempel er α ( G ) uavhengighetsnummeret til en graf; α ′ ( G ) er det samsvarende tallet på grafen, som tilsvarer uavhengighetstallet til linjediagrammet. På samme måte er χ ( G ) det kromatiske tallet på en graf; χ  ′ ( G ) er den kromatiske indeksen til grafen, som tilsvarer det kromatiske tallet på linjediagrammet.

EN

absorberende
Et absorberende sett med en rettet graf er et sett med hjørner slik at for ethvert toppunkt er det en kant fra mot et toppunkt på .
akromatisk
Det akromatiske tallet på en graf er det maksimale antallet farger i en fullstendig fargelegging.
asyklisk
1. En graf er asyklisk hvis den ikke har sykluser. En ikke -styrt asyklisk graf er det samme som en skog . Direkte asykliske grafer kalles sjeldnere asyklisk dirigerte grafer.
2. En asyklisk farging av en ikke -styrt graf er en riktig farging der hver to fargeklasser induserer en skog.
tilstøtningsmatrise
Den naboskapsmatrisen av en kurve som er en matrise hvis rader og søyler er begge indeksert av topp-punktene av grafen, med en i cellen for rad i og kolonne j når topp-punkt i og j er tilstøtende, og en null ellers.
ved siden av
1. Forholdet mellom to hjørner som begge er endepunkter i samme kant.
2. Forholdet mellom to distinkte kanter som deler et endepunkt.
α
For en graf G er α ( G ) (ved hjelp av den greske bokstaven alfa) dens uavhengighetsnummer (se uavhengig ), og α ′ ( G ) er dets matchende nummer (se matching ).
alternerende
I en graf med en matchende er en vekslende bane en bane hvis kanter veksler mellom matchede og umatchede kanter. En vekslende syklus er på samme måte en syklus hvis kanter veksler mellom matchede og umatchede kanter. En forstørrelsesbane er en vekslende bane som starter og slutter ved umettede hjørner. En større matching kan bli funnet som den symmetriske forskjellen mellom matchingen og forstørrelsesbanen; en matching er maksimal hvis og bare hvis den ikke har noen forstørrelsesbane.
antikjede
I en rettet asyklisk graf , en undersett S av hjørner som er parvis uforlignelige, dvs. for alle i S , er det ingen rettet vei fra x til y eller fra y til x . Inspirert av forestillingen om antikjeder i delvis bestilte sett .
anti-kant
Synonym for ikke-kant , et par ikke-tilstøtende hjørner.
antitrekant
Et uavhengig sett med tre vertex, komplementet til en trekant.
toppunkt
1. En toppunktgraf er en graf der ett toppunkt kan fjernes og etterlater et plant undergraf. Det fjernede toppunktet kalles toppunktet. En k -apex -graf er en graf som kan gjøres plan ved å fjerne k -hjørner.
2. Synonym for universal toppunkt , et toppunkt ved siden av alle andre hjørner.
arborescence
Synonym for et rotfestet og regissert tre; se treet .
bue
Se kant .
pil
Et ordnet par av topp-punkt , slik som en kant i en rettet graf . En pil ( x , y ) har en hale x , et hode y og en retning fra x til y ; y sies å være den direkte etterfølgeren til x og x den direkte forgjengeren til y . Pilen ( y , x ) er pilens omvendte pil ( x , y ) .
artikulasjonspunkt
Et toppunkt i en tilkoblet graf hvis fjerning ville koble fra grafen.
-ary
Et k -ary -tre er et rotfestet tre der hvert indre toppunkt ikke har mer enn k -barn. Et 1-ary-tre er bare en sti. Et 2-ary-tre kalles også et binært tre , selv om det begrepet mer riktig refererer til 2-ary-trær der barna til hver node utmerker seg som venstre eller høyre barn (med høyst ett av hver type). Et k -ary -tre sies å være komplett hvis hvert indre toppunkt har nøyaktig k barn.
forsterkning
En spesiell type vekslende bane; se vekslende .
automorfisme
En grafautomorfisme er en symmetri av en graf, en isomorfisme fra grafen til seg selv.

B

bag
Et av settene med hjørner i en nedbrytning av et tre .
balansert
En bipartitt eller flerpartig graf er balansert hvis hver to undergrupper av toppunktpartisjonen har størrelser innenfor hverandre.
båndbredde
Den båndbredden av en graf G er den minimale, over alle orden som hjørnene i G , av lengden av den lengste kanten (antallet trinn i rekkefølgen mellom dens to endepunkter). Det er også en mindre enn størrelsen på den maksimale klikken i et riktig intervall av G , valgt for å minimere klikkestørrelsen.
biclique
Synonym for komplett todelt graf eller komplett todelt undergraf; se komplett .
koblet til hverandre
Vanligvis et synonym for 2 -vertex-tilkoblet , men inkluderer noen ganger K 2 selv om det ikke er 2-tilkoblet. Se tilkoblet ; For komponenter som er koblet sammen , se komponent .
bindende nummer
Det minste mulige forholdet mellom antall naboer til et skikkelig undersett av hjørner og størrelsen på delsettet.
todelt
En topartsgraf er en graf hvis hjørner kan deles i to usammenhengende sett slik at hjørnene i ett sett ikke er koblet til hverandre, men kan være koblet til hjørner i det andre settet. Sagt på en annen måte, en todelt graf er en graf uten merkelige sykluser; tilsvarende er det en graf som kan være riktig farget med to farger. Bipartittgrafer skrives ofte G = ( U , V , E ) hvor U og V er undersettene til hjørnene i hver farge. Imidlertid, med mindre grafen er koblet til, har den kanskje ikke en unik 2-farging.
biregular
En biregulær graf er en todelt graf der det bare er to forskjellige toppunktgrader, en for hvert sett av toppunktet.
blokkere
1. En blokk av en graf G er en maksimal subgraf som enten er et isolert toppunkt, en brokant eller en 2-forbundet subgraf. Hvis en blokk er 2-koblet, tilhører hvert par hjørner i den en felles syklus. Hver kant av en graf hører hjemme i nøyaktig en blokk.
2. Blokkgrafen til en graf G er en annen graf hvis hjørner er blokkene til G , med en kant som forbinder to hjørner når de tilsvarende blokkene deler et artikulasjonspunkt; det er, er det skjæringspunktet graf av blokker av G . Blokkgrafen til en hvilken som helst graf er en skog .
3. Blokken snitt (eller blokk-skjæringspunkt) graf av en graf G er en todelt kurve som der man partite Settet består av cut-punktene av G , og den andre har et topp-punkt for hver blokk av G . Når G er tilkoblet, er blokkens kuttpunktgraf et tre.
4. En blokk graf (også kalt en klikk tre hvis det er koblet, og noen ganger feilaktig kalt en Husimi tre) er et diagram som alle hvis blokkene er fullstendig grafer. En skog er en blokkgraf; så spesielt er blokkgrafen til en hvilken som helst graf en blokkgraf, og hver blokkgraf kan konstrueres som blokkgrafen til en graf.
knytte bånd
Et minimalt kutt-sett : et sett med kanter hvis fjerning kobler fra grafen, som ingen riktig undersett har samme egenskap for.
bok
1. En bok , en bokgraf eller en trekantet bok er en komplett trepartsgraf K 1,1, n ; en samling av n trekanter som er forbundet med en felles kant.
2. En annen type graf, også kalt en bok, eller en firkantet bok, er en samling av 4 -sykler som er forbundet med en felles kant; det kartesiske produktet av en stjerne med en kant.
3. En bokinnbygging er en innebygging av en graf på en topologisk bok, et mellomrom som dannes ved å samle en samling av halvplaner langs en felles linje. Vanligvis må hjørnene til innstøpningen være på linjen, som kalles ryggraden i innstøpningen, og kantene på innstøpningen må ligge i et enkelt halvplan, en av sidene i boken.
bramble
En bramble er en samling av gjensidig berørte tilkoblede undergrafer, der to undergrafer berører hvis de deler et toppunkt eller hver inneholder ett endepunkt på en kant. Rekkefølgen på en bramble er den minste størrelsen på et sett med hjørner som har et ikke -fritt kryss med alle undergrafene. Trebredden på en graf er den maksimale rekkefølgen på noen av dens brambles.
forgrening
En gren-nedbrytning av G er en hierarkisk gruppering av kantene av G , representert ved et binært tre unrooted med bladene merket ved kantene av G . Bredden på en forgrening er maksimum, over kantene e på dette binære treet, av antall delte hjørner mellom undergrafene bestemt av kantene til G i de to undertrærne atskilt med e . Den branchwidth av G er den minste bredde av en hvilken som helst gren-dekomponering av G .
grenbredde
Se forgrening .
bro
1. En bro , isthmus eller skjærkant er en kant hvis fjerning ville koble fra grafen. En brofri graf er en som ikke har broer; tilsvarende en 2-kant-tilkoblet graf.
2. Spesielt i sammenheng med planaritetstesting er en syklusbro en maksimal subgraf som er usammenhengende fra syklusen og der hver to kanter tilhører en bane som er internt skilt fra syklusen. Et akkord er en enkantet bro. En perifer syklus er en syklus med høyst en bro; det må være et ansikt i enhver plan innebygd av grafen.
3. En sykkelbro kan også bety en bane som forbinder to hjørner av en syklus, men er kortere enn en av stiene i syklusen som forbinder de samme to hjørnene. En brobro er en graf der hver syklus med fire eller flere hjørner har en bro.
bridgeless
En brofri graf er en graf som ikke har brokanter ; det vil si en 2-kant-tilkoblet graf .
sommerfugl
1. Sommerfuglgrafen har fem hjørner og seks kanter; den er dannet av to trekanter som deler et toppunkt.
2. Sommerfuglnettverket er en graf som brukes som nettverksarkitektur i distribuert databehandling, nært knyttet til de kubuskoblede syklusene .

C

C
C n er et n -vertex syklus grafen ; se syklus .
kaktus
En Cactus graf , Cactus Tree, Cactus, eller Husimi treet er en tilkoblet diagram hvor hver kant hører til maksimalt én syklus. Blokkene er sykluser eller enkeltkanter. Hvis i tillegg hvert toppunkt tilhører høyst to blokker, kalles det en julekaktus.
bur
Et bur er en vanlig graf med minst mulig rekkefølge for omkretsen.
kanonisk
kanonisering
En kanonisk form av en graf er en invariant slik at to grafer har like invarianter hvis og bare hvis de er isomorfe. Kanoniske former kan også kalles kanoniske invarianter eller komplette invarianter, og er noen ganger definert bare for grafene i en bestemt familie av grafer. Grafkanonisering er prosessen med å beregne en kanonisk form.
kort
En graf dannet fra en gitt graf ved å slette et toppunkt, spesielt i konteksten av rekonstruksjonsformodlingen . Se også kortstokken , flersettet av alle kortene i en graf.
utskjæringsbredde
Carvingbredde er et begrep om grafbredde som er analog med grenbredde, men ved å bruke hierarkiske klynger av hjørner i stedet for hierarkiske klynger av kanter.
larve
Et larvetre eller larve er et tre der de interne nodene induserer en bane.
senter
Den sentrum av en kurve som er et sett av toppunktene minimum eksentrisitet .
kjede
1. Synonym for gange .
2. Når du bruker metoder fra algebraisk topologi til grafer, et element i et kjedekompleks , nemlig et sett med hjørner eller et sett med kanter.
Cheeger konstant
Se utvidelse .
kirsebær
En kirsebær er en bane på tre hjørner.
χ
χ ( G ) (ved bruk av den greske bokstaven chi) er det kromatiske tallet på G og χ  ′ ( G ) er dens kromatiske indeks; se kromatisk og fargelegging .
barn
I et rotfestet tre er et barn av et toppunkt v en nabo til v langs en utgående kant, en som er rettet bort fra roten.
akkord
akkord
1. En akkord av en syklus er en kant som ikke tilhører syklusen, som begge endepunktene tilhører syklusen.
2. En akkordgraf er en graf der hver syklus med fire eller flere hjørner har et akkord, så de eneste induserte syklusene er trekanter.
3. En kraftig akkordgraf er en akkordgraf der hver syklus med lengde seks eller flere har et merkelig akkord.
4. En akkordbipartittgraf er ikke akkordal (med mindre det er en skog); det er en todelt graf der hver syklus med seks eller flere hjørner har et akkord, så de eneste induserte syklusene er 4-sykluser.
5. En akkord av en sirkel er et linjestykke som forbinder to punkter på sirkelen; den krysset grafen av en samling av akkorder kalles en sirkel graf .
kromatisk
Å ha med farging å gjøre; se farge . Kromatisk grafteori er teorien om graffarging. Den kromatiske nummer χ ( G ) er det minste antall farger som trengs i et passende farging av G . χ  '( G ) er det kromatiske indeks av G , minimum antall farger som trengs i en passende kant farging av G .
valgbar
valgbarhet
En graf er k -choosable hvis den har en liste over fargestoffer når hver node har en liste over k tilgjengelige farger. Valgbarheten til grafen er den minste k som den er k -valgbar.
sirkel
En sirkeldiagram er skjæringsgrafen for akkorder i en sirkel.
krets
En krets kan referere til en lukket sti eller et element av syklusen plass (en Eulersk spenner over sub-graf). Den krets rang av en kurve som er den dimensjonen av sin syklus plass.
omkrets
Den omkrets av en kurve som er lengden av den lengste enkel syklus. Grafen er Hamiltonsk hvis og bare hvis omkretsen er lik rekkefølgen.
klasse
1. En klasse med grafer eller en familie av grafer er en (vanligvis uendelig) samling av grafer, ofte definert som grafer som har en bestemt egenskap. Ordet "klasse" brukes i stedet for "sett" fordi, med mindre spesielle begrensninger gjøres (for eksempel å begrense hjørnene som skal tegnes fra et bestemt sett, og definere kanter som sett med to hjørner), er grafer vanligvis ikke sett når den formaliseres ved hjelp av settteori.
2. En fargeklasse for en farget graf er settet med hjørner eller kanter som har en bestemt farge.
3. I sammenheng med Vizinges teorem , på kantfarging av enkle grafer, sies det at en graf er av klasse én hvis den kromatiske indeksen tilsvarer maksimalgraden, og klasse to hvis den kromatiske indeksen er lik en pluss graden. I følge Vizinges teorem er alle enkle grafer enten i klasse én eller klasse to.
klo
En klo er et tre med ett indre toppunkt og tre blader, eller tilsvarende den komplette bipartittgrafen K 1,3 . En klo-fri graf er en graf som ikke har en indusert subgraf som er en klo.
Klikk
En klikk er et sett med gjensidig tilstøtende hjørner (eller hele undergrafen indusert av det settet). Noen ganger er en klikk definert som et maksimalt sett med gjensidig tilstøtende hjørner (eller maksimal komplett subgraf), en som ikke er en del av et større slikt sett (eller subgraf). En k -klikk er en klikk av orden k . Den klikken nummer κ ( G ) for en graf G er i størrelsesorden av sine største gjeng. En klikkgraf er et skjæringsdiagram for maksimale klikk . Se også biclique , en komplett todelt subgraf.
klikketre
Et synonym for en blokkgraf .
klikkbredde
Den klikken-bredde for en graf G er det minste antall adskilte merkelapper som trengs for å konstruere G ved operasjoner som skaper en merket toppunkt, danner disjunkte foreningen av to merkede grafer, legge til en kant som forbinder alle par av topp-punkt med gitte etiketter eller relabel alle hjørner med en gitt etikett. Grafene med klikkbredde på høyst 2 er nøyaktig katalogene .
lukket
1. Et lukket nabolag er et som inkluderer dets sentrale toppunkt; se nabolaget .
2. En lukket tur er en som starter og slutter ved samme toppunkt; se .
3. En graf er midlertidig lukket hvis den tilsvarer sin egen transitive lukking; se transitive .
4. En grafegenskap lukkes under en operasjon på grafer hvis resultatet når argumentet eller argumentene til operasjonen har egenskapen. For eksempel er arvelige egenskaper lukket under induserte undergrafer; monotone egenskaper lukkes under undergrafer; og mindre lukkede eiendommer er stengt under mindreårige.
nedleggelse
1. For transitiv lukking av en rettet graf, se transitive .
2. En lukking av en rettet graf er et sett med hjørner som ikke har utgående kanter til hjørner utenfor lukkingen. For eksempel er en vask en en-toppunkt lukking. Den lukke problem er problemet med å finne en lukking av minimums- eller maksimumsvekt.
med-
Dette prefikset har forskjellige betydninger som vanligvis involverer komplementgrafer . For eksempel er en cograph en graf produsert av operasjoner som inkluderer komplementering; en cocoloring er en farging der hvert toppunkt induserer enten et uavhengig sett (som i riktig farging) eller en klikk (som i en farging av komplementet).
farge
fargelegging
1. En graffarging er en merking av hjørnene i en graf med elementer fra et gitt sett med farger, eller tilsvarende en deling av hjørnene i undersett, kalt "fargeklasser", som hver er knyttet til en av fargene.
2. Noen forfattere bruker "fargelegging", uten kvalifikasjon, til å bety en skikkelig fargelegging, en som tildeler endefarger til hver kant forskjellige farger. I graffarging er målet å finne en riktig farging som bruker så få farger som mulig; for eksempel bipartite grafer er grafene som har fargestoffer med bare to farger, og de fire fargesetningen sier at hver plan graf kan være farget med maksimalt fire farger. En graf sies å være k -farget hvis den har (riktig) farget med k -farger, og k -fargbar eller k -kromatisk hvis dette er mulig.
3. Mange variasjoner av fargestoffer har blitt studert, inkludert kant fargestoffer (fargestoffer kanter, slik at to kanter med samme endepunkt dele en farge), liste farging (riktig fargestoffer med hver node begrenset til et undersett av de tilgjengelige farger), acykliske farging (hver 2-fargede undergraf er asyklisk), samfarging (hver fargeklasse induserer et uavhengig sett eller en klikk), fullstendig farging (hver to fargeklasser deler en kant) og totalfarging (både kanter og hjørner er farget).
4. Fargetallet på en graf er ett pluss degenerasjonen . Det er såkalt fordi det å bruke en grådig fargealgoritme på en degenerasjon av grafen bruker maksimalt så mange farger.
sammenlignbarhet
En ikke -styrt graf er en sammenlignbarhetsgraf hvis dens hjørner er elementene i et delvis ordnet sett og to hjørner er tilstøtende når de er sammenlignbare i delrekkefølgen. Tilsvarende er en sammenlignbarhetsgraf en graf som har en transitiv orientering. Mange andre klasser av grafer kan defineres som sammenligningsgrafer for spesielle typer delordre.
komplement
Den komplement graf av en enkel graf G er en annen graf på samme toppunktet settet som G , med en kant for hver to topp-punkt som ikke er tilstøtende i G .
fullstendig
1. En komplett graf er en der hver to hjørner er tilstøtende: alle kanter som kan eksistere er tilstede. En komplett graf med n hjørner er ofte betegnet K n . En komplett todelt graf er en der hver to hjørner på motsatte sider av partisjonen av hjørner er tilstøtende. En komplett todelte graf med et topp-punkt på den ene side av skilleveggen og b topp-punkt på den andre siden blir ofte betegnet K en , f . Den samme terminologien og notasjonen er også utvidet til å fullføre flerpartsgrafer , grafer der toppunktene er delt inn i mer enn to undersett og hvert par hjørner i forskjellige delmengder er tilstøtende; hvis antallet av hjørner i undergrupper er en , b , c , ... så denne grafen er betegnet K en , b , c , ... .
2. En fullføring av en gitt graf er en supergraf som har noen ønsket egenskap. For eksempel er en akkordfylling et supergraf som er en akkordgraf.
3. En komplett matching er et synonym for en perfekt matching ; se samsvar .
4. En fullstendig farging er en riktig farging der hvert fargefar brukes for endepunktene på minst en kant. Hver farging med et minimum antall farger er fullført, men det kan eksistere komplette farger med større antall farger. Det akromatiske tallet på en graf er det maksimale antallet farger i en fullstendig fargelegging.
5. En komplett invariant av en graf er et synonym for en kanonisk form, en invariant som har forskjellige verdier for ikke-isomorfe grafer.
komponent
En tilkoblet komponent i en graf er en maksimal tilkoblet subgraf. Begrepet brukes også for maksimale undergrafer eller delsett av en grafs hjørner som har en høyere tilkoblingsrekkefølge, inkludert tokoblede komponenter , trikoblede komponenter og sterkt tilkoblede komponenter .
kondensasjon
Den kondensering av en rettet graf G er en rettet asyklisk graf med en topp-punkt for hver sterkt forbundet komponent av G , og en kant som forbinder par av komponenter som inneholder de to endepunktene av minst en kant i G .
Kjegle
En graf som inneholder et universelt toppunkt .
koble
Årsak til å være tilkoblet .
tilkoblet
En tilkoblet graf er en der hvert par hjørner danner endepunktene for en bane. Høyere former for tilkobling inkluderer sterk tilkobling i dirigerte grafer (for hver to hjørner er det stier fra den ene til den andre i begge retninger), k -vertex -tilkoblede grafer (fjerning av færre enn k -hjørner kan ikke koble fra grafen) og k -kant -koblede grafer (fjerning av færre enn k -kanter kan ikke koble fra grafen).
snakke
Den omvendte grafen er et synonym for transponeringsgrafen; se transponering .
kjerne
1. En k -core er den induserte subgrafen som dannes ved å fjerne alle hjørner av grad mindre enn k , og alle hjørner hvis grad blir mindre enn k etter tidligere fjerninger. Se degenerasjon .
2. En kjerne er en graf G slik at hver grafhomomorfisme fra G til seg selv er en isomorfisme.
3. Kjernen i en graf G er en minimal graf H slik at det eksisterer homomorfismer fra G til H og omvendt. H er unik opp til isomorfisme. Den kan representeres som en indusert subgraf av G , og er en kjerne i den forstand at alle dens selvhomomorfismer er isomorfismer.
4. I teorien om grafmatchinger er kjernen i en graf et aspekt av dens nedbrytning av Dulmage - Mendelsohn , dannet som foreningen av alle maksimale matchninger .
cotree
1. Komplementet til et spennende tre .
2. En rotfestet trestruktur som brukes til å beskrive en tavle , hvor hvert krogpunktpunkt er et blad av treet, hver indre node på treet er merket med 0 eller 1, og to kikkerthoder er tilstøtende hvis og bare hvis deres laveste felles stamfar i treet er merket 1.
dekke
Et toppunktdeksel er et sett med hjørner som faller til hver kant i en graf. Et kantdeksel er et sett med kanter som rammer hvert toppunkt i en graf. Et sett med undergrafer av en graf dekker den grafen hvis foreningen -tatt toppunkt- og kantvis-er lik grafen.
kritisk
En kritisk graf for en gitt egenskap er en graf som har egenskapen, men slik at hver subgraf som dannes ved å slette et enkelt toppunkt ikke har egenskapen. For eksempel er en faktor-kritisk graf en som har en perfekt matching (en 1-faktor) for hver toppunktsletting, men (fordi den har et oddetall av hjørner) ikke har noen perfekt matching i seg selv. Sammenlign hypo- , brukt for grafer som ikke har en egenskap, men som hver eneste toppunktsletting gjør.
terning
kubikk
1.   Kubediagram , åtte-toppunktgrafen til hjørnene og kantene på en kube.
2.   Hypercube-graf , en høyere dimensjonal generalisering av terninggrafen.
3.   Brettet kubediagram , dannet av en hyperkube ved å legge til en matchende kobling motsatte hjørner.
4.   Halvert kubediagram , den halve kvadraten i en hyperkubegraf.
5.   Delvis terning , en avstandsbevarende subgraf av en hyperkube.
6. Kuben til en graf G er grafeffekten G 3 .
7.   Kubikkgraf , et annet navn for en 3 -vanlig graf, en der hvert toppunkt har tre innfallskanter.
8.   Kubetilkoblede sykluser , en kubikkgraf dannet ved å erstatte hvert toppunkt i en hyperkube med en syklus.
skjære
kutt-sett
Et kutt er en partisjon av hjørnene i en graf i to undersett, eller settet (også kjent som et kutt-sett) av kanter som strekker seg over en slik partisjon, hvis det settet ikke er tomt. Det sies at en kant strekker seg over partisjonen hvis den har endepunkter i begge delmengdene. Dermed kobler fjerning av et kutt-sett fra en tilkoblet graf det fra.
kuttpunkt
Se artikulasjonspunktet .
kutte plass
Den snitt plass for en graf er et GF (2) - vektorrommet ha cut-settet er i diagrammet som dets elementer og symmetrisk forskjell fra settene som sin vektor addisjonsoperasjon.
syklus
En syklus kan enten referere til en lukket tur (også kalt en tur ) eller mer spesifikt til en lukket tur uten gjentatte hjørner og følgelig kanter (også kalt en enkel syklus). I begge tilfeller blir valget av første toppunkt vanligvis ansett som uviktig: sykliske permutasjoner av turen gir samme syklus. Viktige spesielle tilfeller av sykluser inkluderer Hamiltonian sykluser , induserte sykluser , perifere sykluser og den korteste syklusen, som definerer omkretsen til en graf. En k -sykkel er en syklus med lengden k ; for eksempel er en 2 -syklus en digon og en 3 -syklus er en trekant. En syklusgraf er en graf som i seg selv er en enkel syklus; en syklusgraf med n hjørner er vanligvis betegnet C n . Den syklus plass er et vektorrom generert ved hjelp av enkle sykluser i en graf.

D

DAG
Forkortelse for rettet asyklisk graf , en dirigert graf uten noen rettede sykluser.
Dekk
Multisettet med grafer dannet fra en enkelt graf G ved å slette et enkelt toppunkt på alle mulige måter, spesielt i sammenheng med rekonstruksjonstanken . Et kantdekk dannes på samme måte ved å slette en enkelt kant på alle mulige måter. Grafene i en kortstokk kalles også kort . Se også kritiske (grafer som har en egenskap som ikke er inneholdt av noe kort) og hypo- (grafer som ikke har en egenskap som er beholdt av alle kort).
nedbrytning
Se tre nedbrytning , sti nedbrytning eller gren-nedbrytning .
degenerere
degenerasjon
En k -degenerate grafen er en rettet grafe der hvert induserte sub-graf har minimal grad høyst k . Den degenereringen av en kurve som er den minste k som det er k -degenerate. En degenerasjonsordre er en ordning av toppunktene slik at hvert toppunkt har minimumsgrad i den induserte undergrafen av det og alle senere hjørner; i en degenerasjonsrekkefølge av en k -generert graf, har hvert toppunkt høyst k senere naboer. Degenerasjon er også kjent som k -core -tallet, bredden og koblingen, og ett pluss degenerasjonen kalles også fargetallet eller Szekeres -Wilf -tallet. k -genererte grafer har også blitt kalt k -induktive grafer.
grad
1. Graden av et toppunkt i en graf er dets antall hendende kanter. Graden til en graf G (eller dens maksimale grad) er maksimum for gradene på dens hjørner, ofte betegnet Δ ( G ) ; minimumsgraden av G er minimum av dens toppunktgrader, ofte betegnet δ ( G ) . Grad kalles noen ganger valens ; graden av v i G kan betegnes d G ( v ) , d ( G ) eller deg ( v ) . Den totale graden er summen av gradene til alle hjørner; ved handshaking lemma er det et partall. Den grad sekvens er samlingen av alle grader av topp-punkt, i sortert orden fra størst til minst. I en rettet graf kan man skille mellom grader (antall innkommende kanter) og ut-grader (antall utgående kanter).
2. Homomorfismegraden til en graf er et synonym for Hadwiger -nummeret , rekkefølgen til den største clique -minor .
Δ, δ
Δ ( G ) (ved hjelp av den greske bokstaven delta) er den maksimale graden av et toppunkt i G , og δ ( G ) er minimumsgraden; se grad .
tetthet
I en graf over n noder er tettheten forholdet mellom antall kanter på grafen og antall kanter i en komplett graf på n noder. Se tett graf .
dybde
Dybden på en node i et rotfestet tre er antall kanter i banen fra roten til noden. For eksempel er rotens dybde 0 og dybden til en av dens tilstøtende noder er 1. Det er nivået til en node minus en. Vær imidlertid oppmerksom på at noen forfattere i stedet bruker dybde som et synonym for nivået på en node.
diameter
Diameteren til en tilkoblet graf er maksimal lengde på den korteste banen . Det vil si at det er maksimum av avstandene mellom par av hjørner i grafen. Hvis grafen har vekter på kantene, måler dens veide diameter banelengden med summen av kantvektene langs en bane, mens den uvektede diameteren måler banelengden med antall kanter. For frakoblede grafer varierer definisjoner: Diameteren kan defineres som uendelig, eller som den største diameteren til en tilkoblet komponent, eller den kan være udefinert.
diamant
The diamond grafen er en urettet graf med fire hjørner og fem kanter.
koblet til
Sterk ly tilkoblet . (For ikke å forveksle med frakoblet )
digon
En digon er en enkel syklus med lengde to i en rettet graf eller en multigraf. Digoner kan ikke forekomme i enkle uorienterte grafer, ettersom de krever at den samme kanten gjentas to ganger, noe som bryter definisjonen av enkel .
digraph
Synonym for regissert graf .
dipat
Se rettet vei .
direkte forgjenger
Halen på en rettet kant hvis hode er det gitte toppunktet.
direkte etterfølger
Hodet på en rettet kant hvis hale er det gitte toppunktet.
rettet
En rettet graf er en der kantene har en distinkt retning, fra et toppunkt til et annet. I en blandet graf er en rettet kant igjen en som har en utmerket retning; rettet kant kan også kalles buer eller piler.
regissert bue
Se pil .
rettet kant
Se pil .
rettet linje
Se pil .
rettet vei
En bane hvor alle kant s har den samme retning . Hvis en rettet vei fører fra toppunkt x til toppunkt y , er x en forgjenger for y , y er en etterfølger av x , og y sies å være tilgjengelig fra x .
retning
1. Det asymmetriske forholdet mellom to tilstøtende hjørner i en graf , representert som en pil .
2. Det asymmetriske forholdet mellom to hjørner i en rettet bane .
koble fra
Årsak til å bli frakoblet .
frakoblet
Ikke tilkoblet .
usammenhengende
1. To undergrafer er kantskjønne hvis de ikke deler kanter, og toppunktet skiller seg ut hvis de ikke deler hjørner.
2. Den usammenhengende foreningen av to eller flere grafer er en graf hvis toppunkt og kantsett er de usammenhengende foreningene til de tilsvarende settene.
avstand
Den avstand mellom hvilke som helst to topp-punkt i en kurve som er lengden av den korteste veien å ha de to topp-punktene som sine endepunkter.
domatisk
En domatisk partisjon av en graf er en partisjon av toppunktene i dominerende sett. Det domatiske tallet på grafen er det maksimale antallet dominerende sett i en slik partisjon.
dominerende
Et dominerende sett er et sett med hjørner som inkluderer eller er i tilknytning til hvert toppunkt i grafen; ikke å forveksle med et toppunktdeksel, et toppunktsett som rammes av alle kantene i grafen. Viktige spesielle typer dominerende sett inkluderer uavhengige dominerende sett (dominerende sett som også er uavhengige sett) og tilkoblede dominerende sett (dominerende sett som induserte tilkoblede subgrafer). Et dominerende sett med ett toppunkt kan også kalles et universelt toppunkt. Domineringsnummeret til en graf er antall hjørner i det minste dominerende settet.

E

E
E ( G ) er kantsettet til G ; se kantsett .
øre
Et øre på en graf er en bane hvis endepunkter kan falle sammen, men der det ellers ikke er gjentagelser av hjørner eller kanter.
nedbrytning av øret
En øredekomponering er en inndeling av kantene på en graf i en sekvens av ører, som hver av endepunktene (etter det første) tilhører et tidligere øre og hver av sine indre punkter ikke tilhører et tidligere øre. Et åpent øre er en enkel bane (et øre uten gjentatte hjørner), og et åpent øre -dekomponering er en nedbrytning av øret der hvert øre etter det første er åpent; en graf har et åpent øret dekomponering hvis og bare hvis den er koblet til hverandre. Et øre er merkelig hvis det har et oddetall på kanter, og et ulikt nedbrytning av øret er en nedbrytning av øret der hvert øre er merkelig; en graf har en merkelig ørededbrytning hvis og bare hvis den er faktorkritisk.
eksentrisitet
Eksentrisiteten til et toppunkt er den lengste avstanden fra det til et annet toppunkt.
kant
En kant er (sammen med hjørner) en av de to grunnleggende enhetene som grafer er konstruert av. Hver kant har to (eller i hypergrafer, flere) hjørner som den er festet til, kalt dens endepunkter. Kanter kan være rettet eller ikke -rettet; uorienterte kanter kalles også linjer og dirigerte kanter kalles også buer eller piler. I en ikke -dirigert enkel graf kan en kant representeres som settet med dens hjørner, og i en enkel, direkte graf kan den bli representert som et ordnet par av dens hjørner. En kant som forbinder hjørner x og y er noen ganger skrevet xy .
kantklipp
Et sett med kant s hvis fjerning kobler fra grafen . Et enkantskutt kalles en bro , isthmus eller skjærkant .
kant sett
Settet med kanter på en gitt graf G , noen ganger betegnet med E ( G ) .
kantløs graf
Den kantløse grafen eller den totalt frakoblede grafen på et gitt sett med hjørner er grafen som ikke har noen kanter. Det kalles noen ganger den tomme grafen, men dette begrepet kan også referere til en graf uten hjørner.
innebygd
En grafinnebygging er en topologisk fremstilling av en graf som en delmengde av et topologisk rom med hvert toppunkt representert som et punkt, hver kant representert som en kurve som har endepunktene til kanten som endepunkter for kurven, og ingen andre kryss mellom hjørner eller kanter. En plan graf er en graf som har en slik innebygging på det euklidiske planet, og en toroidal graf er en graf som har en slik innebygging på en torus. Den genus av en kurve som er minst mulig slekten av en to-dimensjonal manifold på hvilken det kan bygges inn.
tom graf
1. En kantløs graf på et sett med uendelige hjørner.
2. Ordre-null-grafen , en graf uten hjørner og uten kanter.
slutt
En ende av en uendelig grafen er en ekvivalens klasse av stråler, hvor to stråler som er ekvivalente hvis det er en tredje stråle som har uendelig mange toppunkter fra dem begge.
endepunkt
En av de to hjørnene forbundet med en gitt kant, eller en av det første eller siste toppunktet på en tur, sti eller sti. Det første endepunktet for en gitt rettet kant kalles halen og det andre endepunktet kalles hodet .
oppregning
Grafoppregning er problemet med å telle grafer i en gitt klasse grafer, som en funksjon av rekkefølgen deres. Mer generelt kan oppregningsproblemer referere enten til problemer med å telle en bestemt klasse kombinatoriske objekter (for eksempel klikk, uavhengige sett, fargestoffer eller spennende trær), eller algoritmisk oppføring av alle slike objekter.
Eulerian
En Eulerian -bane er en tur som bruker hver kant av en graf nøyaktig én gang. En Eulerian -krets (også kalt en Eulerian -syklus eller en Euler -tur) er en lukket tur som bruker hver kant nøyaktig en gang. En Eulerian -graf er en graf som har en Eulerian -krets. For en ikke -styrt graf betyr dette at grafen er koblet til og hvert toppunkt har jevn grad. For en rettet graf betyr dette at grafen er sterkt koblet og hvert toppunkt har grad som er lik ut-graden. I noen tilfeller løsnes tilkoblingskravet, og en graf som bare oppfyller gradskravene kalles Eulerian.
til og med
Delelig med to; for eksempel er en jevn syklus en syklus hvis lengde er jevn.
ekspander
En ekspanderingsgraf er en graf hvis kantutvidelse, toppunktsutvidelse eller spektral ekspansjon er avgrenset fra null.
ekspansjon
1. Den kant ekspansjon, isoperimetric nummer, eller Cheeger konstant for en graf G er minimumsforholdet, over undergrupper S på maksimalt halvparten av topp-punktene av G , av antallet av kanter som forlater S til antallet av hjørner i S .
2. Toppekspansjonen, toppunktet isoperimetrisk tall eller forstørrelsen av en graf G er minimumsforholdet, over undersett S på høyst halvparten av toppunktene til G , av antall hjørner utenfor, men i tilknytning til S, til antall hjørner i S .
3. Den unike nabo utvidelse av en graf G er minimumsforholdet, over undergrupper av høyst halvparten av topp-punktene av G , av antallet av hjørner utenfor S , men i tilknytning til en unik topp-punkt i S til antallet av hjørner i S .
4. Spektral ekspansjonen til en d -regulær graf G er spektralgapet mellom den største egenverdien d av dens adjacensmatrise og den nest største egenverdien.
5. En familie av grafer har begrenset ekspansjon hvis alle dens r -grunne mindreårige har et forhold mellom kanter og hjørner begrenset av en funksjon av r , og polynom ekspansjon hvis funksjonen til r er et polynom.

F

ansikt
I en plangraf eller en grafinnbinding er en tilkoblet komponent i delsettet av planet eller overflaten av innstøpningen som er skilt fra grafen. For en innebygging i flyet vil alle unntatt ett ansikt være avgrenset; det eneste eksepsjonelle ansiktet som strekker seg til det uendelige kalles det ytre ansiktet.
faktor
En faktor i en graf er en spennende subgraf: en subgraf som inkluderer alle hjørnene i grafen. Begrepet brukes først og fremst i sammenheng med vanlige undergrafer: en k -faktor er en faktor som er k -regelmessig. Spesielt er en 1 -faktor det samme som en perfekt matching. En faktor -kritisk graf er en graf som sletter et hvilket som helst toppunkt gir en graf med en 1 -faktor.
faktorisering
En graffaktorisering er en inndeling av kantene på grafen i faktorer; en k -faktorisering er en inndeling i k -faktorer. For eksempel en 1 -factorization er en kant fargelegging med den ytterligere egenskap at hver node er innfallende på en kant av hver farge.
familie
Et synonym for klassen .
avgrenset
En graf er begrenset hvis den har et begrenset antall hjørner og et begrenset antall kanter. Mange kilder antar at alle grafer er begrensede uten å si det eksplisitt. En graf er lokalt endelig hvis hvert toppunkt har et begrenset antall innfallskanter. En uendelig graf er en graf som ikke er begrenset: den har uendelig mange hjørner, uendelig mange kanter eller begge deler.
første orden
Den første ordens logikk for grafer er en form for logikk der variabler representerer hjørner av en graf, og det finnes et binært predikat for å teste om to hjørner er tilstøtende. For å skille seg fra andre ordens logikk, der variabler også kan representere sett med hjørner eller kanter.
-klaff
For et sett med noder X , en X er -flap en tilkoblet komponent av den induserte sub-graf som dannes ved å slette X . Klaffterminologien brukes ofte i forbindelse med havner , funksjoner som kartlegger små sett med hjørner til klaffene deres. Se også broen til en syklus, som enten er en klaff på sykluspunktene eller et akkord av syklusen.
forbudt
En forbudt grafkarakterisering er en karakterisering av en familie av grafer som grafer som ikke har visse andre grafer som undergrafer, induserte undergrafer eller mindreårige. Hvis H er en av grafene som ikke forekommer som en subgraf, indusert subgraf eller mindre, sies det at H er forbudt.
skog
En skog er en ikke -dirigert graf uten sykluser (en usammenhengende forening av ikke -rotte trær), eller en rettet graf dannet som en usammenhengende forening av forankrede trær.
Frucht
1.   Robert Frucht
2. Frucht -grafen , en av de to minste kubikkgrafene uten utilsiktede symmetrier.
3.   Frucht's teorem om at hver begrenset gruppe er gruppen av symmetrier i en endelig graf.
full
Synonym for induced .
funksjonell graf
En funksjonell graf er en rettet graf der hvert toppunkt har en utgravd. Tilsvarende er en funksjonell graf en maksimal rettet pseudoforest.

G

G
En variabel som ofte brukes til å markere en graf.
slekt
Slekten til en graf er den minste slekten til en overflate som den kan legges inn på; se innebygging .
geodesisk
Som et substantiv er en geodesikk et synonym for en korteste vei . Når det brukes som et adjektiv, betyr det relatert til korteste stier eller korteste baneavstander.
kjempe
I teorien om tilfeldige grafer er en gigantisk komponent en tilkoblet komponent som inneholder en konstant brøkdel av grafens hjørner. I standardmodeller av tilfeldige grafer er det vanligvis høyst en gigantisk komponent.
omkrets
Den omkrets av en kurve som er lengden av den korteste syklusen.
kurve
Det grunnleggende studieobjektet i grafteori, et system med hjørner som er parvis forbundet med kanter. Ofte inndelt i dirigerte grafer eller uorienterte grafer i henhold til om kantene har en retning eller ikke. Blandede grafer inkluderer begge typer kanter.
grådig
Produsert av en grådig algoritme . For eksempel er en grådig farging av en graf en farging produsert ved å vurdere hjørnene i en viss sekvens og tildele hvert toppunkt den første tilgjengelige fargen.
Grötzsch
1.   Herbert Grötzsch
2. Grötzsch-grafen , den minste trekantfrie grafen som krever fire farger i riktig farge.
3.   Grötzschs teorem om at trekantfrie plane grafer alltid kan farges med høyst tre farger.
Grundy nummer
1. Grundy-tallet i en graf er det maksimale antallet farger som produseres av en grådig farging , med en dårlig valgt toppunktsrekkefølge.

H

H
En variabel ofte brukt for å betegne en graf, spesielt når en annen graf som allerede har blitt betegnet med G .
H -farging
En H -coloring av en graf G (hvor H er også en graf) er en homomorfi fra H til G .
H -gratis
En graf er H -fri hvis den ikke har en indusert subgraf som er isomorf for H , det vil si hvis H er en forbudt indusert subgraf. De H -fri grafene er familien av alle grafer (eller, ofte, alle endelige grafer) som er H -fritt. For eksempel er de trekantfrie grafene grafene som ikke har en trekantsgraf som undergraf. Egenskapen til å være H -fri er alltid arvelig. En graf er H -Mindre fritt hvis den ikke har en mindre isomorf med H .
Hadwiger
1.   Hugo Hadwiger
2. Hadwiger -tallet i en graf er rekkefølgen til den største komplette minor på grafen. Det kalles også sammentrekningsklikketallet eller homomorfismen.
3. Hadwiger -formodningen er formodningen om at Hadwiger -tallet aldri er mindre enn det kromatiske tallet.
Hamiltonian
En Hamiltonsk bane eller Hamiltonian syklus er en enkel spenningsbane eller enkel spenningssyklus: den dekker alle hjørnene i grafen nøyaktig en gang. En graf er Hamiltonian hvis den inneholder en Hamiltonian syklus, og sporbar hvis den inneholder en Hamiltonian bane.
tilfluktssted
En k - haven er en funksjon som kartlegger hvert sett X med færre enn k -hjørner til en av klaffene, og tilfredsstiller ofte ytterligere konsistensbetingelser. Ordenen til et fristed er tallet k . Havner kan brukes til å karakterisere trebredden til endelige grafer og endene og Hadwiger -tallene på uendelige grafer.
høyde
1. Høyden på en node i et rotfestet tre er antall kanter i en maksimal bane, som går bort fra roten (dvs. at nodene har en sterkt økende dybde), som starter ved den noden og slutter ved et blad.
2. Høyden på et rotfestet tre er høyden på roten. Det vil si at høyden på et tre er antall kanter på en lengst mulig bane, som går bort fra roten, som starter ved roten og slutter ved et blad.
3. Høyden på en rettet asyklisk graf er den maksimale lengden på en rettet bane i denne grafen.
arvelig
En arvelig egenskap av grafer er en egenskap som er stengt etter indusert subgraphs: hvis G har en arvelig egenskap, og så må hver indusert subgraf av G . Sammenlign monoton (lukket under alle undergrafer) eller mindre lukkede (lukket under mindreårige).
sekskant
En enkel syklus som består av nøyaktig seks kanter og seks hjørner.
hull
Et hull er en indusert syklus med lengde fire eller mer. Et merkelig hull er et hull med ulik lengde. Et anti-hull er en indusert subgraf av orden fire hvis komplement er en syklus; tilsvarende er det et hull i komplementgrafen. Denne terminologien brukes hovedsakelig i sammenheng med perfekte grafer, som er preget av den sterke perfekte grafsetningen som grafene uten merkelige hull eller merkelige antihull. De hullfrie grafene er de samme som akkordgrafene .
homomorf ekvivalens
To grafer er homomorfe ekvivalente hvis det finnes to homomorfismer, en fra hver graf til den andre grafen.
homomorfisme
1. En grafhomomorfisme er en kartlegging fra toppunktet til en graf til toppunktet til en annen graf som kartlegger tilstøtende hjørner til tilstøtende hjørner. Denne typen kartlegging mellom grafer er den som er mest brukt i kategoriteoretiske tilnærminger til grafteori. En riktig graffarging kan ekvivalent beskrives som en homomorfisme til en komplett graf.
2. Homomorfismegraden til en graf er et synonym for Hadwiger -nummeret , rekkefølgen til den største clique -minor .
hyperkant
En kant i en hypergrafi , som har et hvilket som helst antall endepunkter, i motsetning til kravet om at kanter på grafer har nøyaktig to endepunkter.
hyperkube
En hyperkubegraf er en graf dannet fra hjørnene og kantene på en geometrisk hyperkube .
hypergraf
En hypergraf er en generalisering av en graf der hver kant (kalt en hyperkant i denne sammenhengen) kan ha mer enn to endepunkter.
hypo-
Dette prefikset, i kombinasjon med en grafegenskap, indikerer en graf som ikke har egenskapen, men slik at hver subgraf som dannes ved å slette et enkelt toppunkt, har egenskapen. For eksempel er en hypohamiltonsk graf en som ikke har en hamiltonsyklus, men som hver slettning med en toppunkt gir en Hamiltonian subgraf for. Sammenlign kritisk , brukt for grafer som har en egenskap, men som hver eneste toppunkt sletting ikke gjør.

Jeg

i grad
Antall innkommende kanter i en rettet graf; se grad .
forekomst
En forekomst i en graf er et toppunkt-kantpar slik at toppunktet er et endepunkt for kanten.
forekomstmatrise
Den forekomsten matrise av en graf er en matrise hvis rader er indeksert ved toppunktene til kurven, og hvis kolonner er indeksert ved kantene, med en i cellen for rad i og kolonne j når toppunktet i og kanten j er innfallende, og en null ellers.
hendelse
Forholdet mellom en kant og et av endepunktene.
uforlikelighet
En uforlikelighetsgraf er komplementet til en sammenligningsgraf ; se sammenlignbarhet .
uavhengig
1. Et uavhengig sett er et sett med hjørner som induserer en kantløs subgraf. Det kan også kalles et stabilt sett eller en coclique. Den uavhengighet nummer α ( G ) er størrelsen av den maksimale uavhengig sett .
2. I den grafiske matroiden til en graf er et delsett av kanter uavhengig hvis den tilsvarende undergrafen er et tre eller en skog. I den bicircular matroid er et delsett av kanter uavhengig hvis den tilsvarende undergrafen er en pseudoforest .
likegyldighet
En likegyldighetsgraf er et annet navn på en riktig intervallgraf eller enhetsintervallgraf; se riktig .
indusert
En indusert subgraf eller full delgraf av en graf er en subgraf dannet fra en undersett av hjørner og fra alle kantene som har begge endepunktene i delsettet. Spesielle tilfeller inkluderer induserte stier og induserte sykluser , induserte undergrafer som er stier eller sykluser.
induktiv
Synonym for degenerert .
uendelig
En uendelig graf er en som ikke er endelig; se endelig .
innvendig
Et toppunkt på en sti eller et tre er internt hvis det ikke er et blad; det vil si hvis graden er større enn en. To veier er internt usammenhengende (noen kaller det uavhengige ) hvis de ikke har noen toppunkt felles, bortsett fra den første og den siste.
kryss
1. Skjæringspunktet mellom to grafer er deres største vanlige undergraf, grafen dannet av hjørnene og kantene som tilhører begge grafer.
2. En skjæringsgraf er en graf hvis hjørner samsvarer med sett eller geometriske objekter, med en kant mellom to hjørner nøyaktig når de to tilsvarende settene eller objektene har et ikke -fritt kryss. Flere klasser av grafer kan defineres som skjæringsgrafer for bestemte typer objekter, for eksempel akkordgrafer (skjæringsgrafer for undertre av et tre), sirkeldiagrammer (skjæringsgrafer for akkorder i en sirkel), intervallgrafer (skjæringsgrafer med intervaller av en linje), linjediagrammer (skjæringsgrafer for kantene på en graf) og klikkgrafer (skjæringsgrafer for de maksimale klikkene i en graf). Hver graf er et skjæringsgraf for noen grupper av sett, og denne familien kalles en skjæringsrepresentasjon av grafen. Den kryssnummer for en graf G er den minimale totale antall elementer i et hvilket som helst skjærings fremstilling av G .
intervall
1. En intervallgraf er en skjæringsgraf med intervaller på en linje .
2. Intervallet [ u , v ] i en graf er foreningen av alle korteste veier fra u til v .
3. Intervalltykkelse er et synonym for banebredde .
uforanderlig
Et synonym for eiendom .
invertert pil
En pil med motsatt retning sammenlignet med en annen pil. Pilen ( y , x ) er pilens omvendte pil ( x , y ) .
isolert
Et isolert toppunkt i en graf er et toppunkt hvis grad er null, det vil si et toppunkt uten innfallende kanter.
isomorf
To grafer er isomorfe hvis det er en isomorfisme mellom dem; se isomorfisme .
isomorfisme
En grafisomorfisme er en en-til-en-forekomst som bevarer korrespondansen mellom hjørnene og kantene på en graf til hjørnene og kantene på en annen graf. To grafer relatert på denne måten sies å være isomorfe.
isoperimetrisk
Se utvidelse .
isthmus
Synonym for bridge , i betydningen en kant hvis fjerning kobler fra grafen.

K

K
For notasjonen for komplette grafer, komplette topartsgrafer og komplette flerpartsgrafer, se komplett .
κ
κ ( G ) (ved hjelp av den greske bokstaven kappa) er rekkefølgen på maksimal klikk i G ; se klikk .
kjernen
En kjerne i en rettet graf er et sett med hjørner som er både stabilt og absorberende .
knute
En uunngåelig seksjon av en rettet graf . Se knute (matematikk) og knute teori .

L

L
L ( G ) er linjediagrammet til G ; se linje .
merkelapp
1. Informasjon knyttet til et toppunkt eller en kant av en graf. En merket graf er en graf hvis hjørner eller kanter har etiketter. Begrepene toppunktsmerket eller kantmerket kan brukes til å spesifisere hvilke objekter i en graf som har etiketter. Grafmerking viser til flere forskjellige problemer med å tilordne etiketter til grafer som er underlagt visse begrensninger. Se også graffarging , der etikettene tolkes som farger.
2. I sammenheng med grafoppregning sies det at hjørnene i en graf er merket hvis de alle kan skilles fra hverandre. Dette kan for eksempel gjøres sant ved å fikse en en-til-en-korrespondanse mellom toppunktene og heltallene fra 1 til grafens rekkefølge. Når hjørner er merket, telles grafer som er isomorfe for hverandre (men med forskjellige toppunktsordninger) som separate objekter. I kontrast, når hjørnene er umerkede, teller grafer som er isomorfe for hverandre ikke separat.
blad
1. Et bladpunkt eller et hengende toppunkt (spesielt i et tre) er et toppunkt hvis grad er  1 . En bladkant eller hengende kant er kanten som forbinder et bladpunkt til sin eneste nabo.
2. Et bladets kraft til et tre er en graf hvis hjørner er bladene på treet og hvis kanter forbinder blader hvis avstand i treet høyst er en gitt terskel.
lengde
I en uvektet graf er lengden på en syklus, sti eller gåing antall kanter den bruker. I en vektet graf kan det i stedet være summen av kantene som den bruker. Lengde brukes til å definere den korteste banen , omkretsen (korteste sykluslengden) og den lengste banen mellom to hjørner i en graf.
nivå
1. Dette er dybden til en node pluss 1, selv om noen definerer den i stedet for å være synonym for dybde . En nodes nivå i et forankret tre er antall noder i banen fra roten til noden. For eksempel har roten nivå 1 og en av dens tilstøtende noder har nivå 2.
2. Et sett med alle noder som har samme nivå eller dybde.
linje
Et synonym for en ustyrt kant. Den linjediagram L ( G ) for en graf G er en graf med et topp-punkt for hver kant av G , og en kant for hvert par av kanter som deler et endepunkt i G .
kobling
Et synonym for degenerasjon .
liste
1. En tilstøtende liste er en datamaskinrepresentasjon av grafer for bruk i grafalgoritmer.
2.   Listfarging er en variant av graffarging der hvert toppunkt har en liste over tilgjengelige farger.
lokal
En lokal eiendom til en graf er en egenskap som bare bestemmes av nabolagene til hjørnene i grafen. For eksempel er en graf lokalt endelig hvis alle nabolagene er begrensede.
Løkke
En sløyfe eller selvløkke er en kant som begge endepunktene er det samme toppunktet. Den danner en syklus med lengde 1 . Disse er ikke tillatt i enkle grafer.

M

forstørrelse
Synonym for toppunktet ekspansjon .
matchende
En matching er et sett med kanter der ingen deler noe toppunkt. Et toppunkt er matchet eller mettet hvis det er et av endepunktene til en kant i matchingen. En perfekt matching eller komplett matching er en matching som matcher hvert toppunkt; det kan også kalles en 1-faktor, og kan bare eksistere når rekkefølgen er jevn. En nesten perfekt matching, i en graf med ulik rekkefølge, er en som metter alle unntatt ett toppunkt. En maksimal matching er en matching som bruker så mange kanter som mulig; det matchende tallet α ′ ( G ) i en graf G er antall kanter i en maksimal matching. En maksimal matching er en matchning som det ikke kan legges til ytterligere kanter.
maksimal
1. En subgraf av den gitte grafen G er maksimal for en bestemt egenskap hvis den har den egenskapen, men ingen annen supergraf av den som også er en subgraf av G , har også den samme egenskapen. Det vil si at det er et maksimalt element i undergrafene med eiendommen. For eksempel er en maksimal klikk en komplett subgraf som ikke kan utvides til en større komplett subgraf. Ordet "maksimal" bør skilles fra "maksimum": en maksimal subgraf er alltid maksimal, men ikke nødvendigvis omvendt.
2. En enkel graf med en gitt egenskap er maksimal for den egenskapen hvis det ikke er mulig å legge til flere kanter på den (holde toppunktet uendret) samtidig som både grafens enkelhet og egenskapen bevares. Således er for eksempel en maksimal plan graf en plan graf slik at hvis du legger til flere kanter på den, vil det opprette en ikke-plan graf.
maksimum
Et undergraf for en gitt graf G er maksimum for en bestemt egenskap hvis den er den største undergrafen (etter rekkefølge eller størrelse) blant alle undergrafer med den egenskapen. For eksempel er en maksimal klikk en av de største klikkene i en gitt graf.
median
1. En median på en trippel av hjørner, et toppunkt som tilhører de korteste veiene mellom alle parene av hjørner, spesielt i mediangrafer og modulgrafer .
2. En median graf er en graf der hver tredje toppunkt har en unik median.
Meyniel
1. Henri Meyniel, fransk grafteoretiker.
2. En Meyniel -graf er en graf der hver oddssyklus med lengde fem eller flere har minst to akkorder.
minimal
En undergrafi av en gitt graf er minimal for en bestemt eiendom hvis den har den egenskapen, men ingen skikkelig undergrav av den har også den samme egenskapen. Det vil si at det er et minimalt element i undergrafene med eiendommen.
minimum kutt
Et kutt hvis kutt-sett har minimum totalvekt, muligens begrenset til kutt som skiller et angitt par hjørner; de er preget av max-flow min-cut teoremet .
liten
En graf H er et mindre av en annen graf G hvis H kan oppnås ved å slette kanter eller spisser fra G og kontrahering kanter i G . Det er en grunne minor hvis den kan dannes som en minor på en slik måte at subgrafiene til G som ble kontrahert for å danne hjørner av H alle har liten diameter. H er et topologisk mindre av G hvis G har en subgraf som er en underavdeling av H . En graf er H -mindre -fri hvis den ikke har H som minor. En familie av grafer lukkes mindre hvis den lukkes under mindreårige; den Robertson-Seymour teoremet karakteriserer mindre lukket familier som har et begrenset sett av forbudte mindreårige.
blandet
En blandet graf er en graf som kan inneholde både rettet og ikke -rettet kant.
modulær
1.   Modulær graf , en graf der hver trippel av hjørner har minst ett median toppunkt som tilhører de korteste veiene mellom alle parene i trippelen.
2.   Modulær dekomponering , en dekomponering av en graf til undergrafer der alle hjørner kobles til resten av grafen på samme måte.
3.   Modularitet av en grafgruppering, forskjellen mellom antall kryss-klyngekanter fra den forventede verdien.
monoton
En monoton eiendom grafer er en egenskap som er stengt etter subgraphs: hvis G har en arvelig egenskap, og så må hver subgraf av G . Sammenlign arvelig (lukket under induserte undergrafer) eller mindre lukkede (lukket under mindreårige).
Moore -graf
En Moore -graf er en vanlig graf som Moore -grensen er nøyaktig oppfylt for. Moore -grensen er en ulikhet knyttet til graden, diameteren og rekkefølgen på en graf, bevist av Edward F. Moore . Hver Moore -graf er et bur.
multigraf
En multigraf er en graf som tillater flere adjakenser (og ofte selvløkker); en graf som ikke er nødvendig for å være enkel.
flere tilstøtende
En flertalls tilknytning eller flere kanter er et sett med mer enn en kant som alle har de samme endepunktene (i samme retning, når det gjelder rettet grafer). En graf med flere kanter kalles ofte en multigraf.
mangfold
Mangfoldet av en kant er antall kanter i en multipel adjacency. Multiplikiteten til en graf er den maksimale mangfoldigheten av noen av kantene.

N

N
1. For notasjonen for åpne og lukkede nabolag, se nabolag .
2. En liten n brukes ofte (spesielt innen informatikk) for å angi antall hjørner i en gitt graf.
nabo
nabo
Et toppunkt som grenser til et gitt toppunkt.
nabolag
nabolag
Det åpne nabolaget (eller nabolaget) til et toppunkt v er subgrafen indusert av alle hjørner som ligger ved siden av v . Det lukkede nabolaget er definert på samme måte, men inkluderer også v selv. Det åpne nabolaget v i G kan betegnes N G ( v ) eller N ( v ) , og det lukkede nabolaget kan betegnes N G [ v ] eller N [ v ] . Når åpenhet eller lukkethet i et nabolag ikke er spesifisert, antas det å være åpent.
Nettverk
En graf der attributter (f.eks. Navn) er knyttet til nodene og/eller kantene.
node
Et synonym for toppunkt .
ikke-kant
En ikke-kant eller antikant er et par hjørner som ikke er tilstøtende; kantene på komplementgrafen.
null graf
Se tom graf .

O

merkelig
1. En oddssyklus er en syklus hvis lengde er oddetall. Den merkelige omkretsen til en ikke-todelt graf er lengden på den korteste odde syklusen. Et merkelig hull er et spesielt tilfelle av en oddssyklus: en som er indusert og har fire eller flere hjørner.
2. Et merkelig toppunkt er et toppunkt hvis grad er oddetall. Ved håndrystende lemma har hver begrenset, uorientert graf et jevnt antall oddetall.
3. Et merkelig øre er en enkel bane eller enkel syklus med et oddetall kant, som brukes i dekomposisjoner av odd-ear av faktor-kritiske grafer; se øret .
4. Et merkelig akkord er en kant som forbinder to hjørner som er en ulik avstand fra hverandre i en jevn syklus. Merkelige akkorder brukes til å definere kraftige akkordgrafer .
5. En odde kurve som er et spesialtilfelle av en Kneser graf , som har en toppunktet for hver ( n - 1) -elementer delsett av et (2 n - 1) -elementer sett, og en kant som forbinder to undergrupper når deres tilsvarende sett er usammenhengende.
åpen
1. Se nabolaget .
2. Se gåtur .
rekkefølge
1. Rekkefølgen på en graf G er tallet på dens hjørner, | V ( G ) | . Variabelen n brukes ofte for denne mengden. Se også størrelse , antall kanter.
2. En type logikk av grafer ; se første og andre ordre .
3. En rekkefølge eller rekkefølge av en graf er et arrangement av dets hjørner i en sekvens, spesielt i sammenheng med topologisk orden (en rekkefølge av en rettet asyklisk graf der hver kant går fra et tidligere toppunkt til et senere toppunkt i rekkefølgen ) og degenerasjonsrekkefølge (en rekkefølge der hvert toppunkt har minimumsgrad i den induserte undergrafen av det og alle senere hjørner).
4. For rekkefølgen av et fristed eller bramble, se tilfluktssted og bramble .
orientering
orientert
1. En orientering av en ikke -styrt graf er en tildeling av retninger til kantene, slik at den blir til en rettet graf. En orientert graf er en som har blitt tildelt en orientering. Så, for eksempel, er et polytree et orientert tre; det skiller seg fra et rettet tre (en arborescence) ved at det ikke er krav om konsistens i kantene. Andre spesielle typer orientering inkluderer turneringer , orienteringer av komplette grafer; sterke orienteringer , orienteringer som er sterkt forbundet; asykliske orienteringer , orienteringer som er asykliske; Eulerian orienteringer , orienteringer som er Eulerian; og transitive orienteringer , retninger som er midlertidig lukket.
2. Orientert graf, brukt av noen forfattere som et synonym for en rettet graf .
ut-grad
Se grad .
ytre
Se ansiktet .
ytre plan
En ytre plan graf er en graf som kan legges inn i planet (uten kryss) slik at alle hjørner er på grafens ytre side.

P

sti
En sti kan enten være en tur eller en tur uten gjentatte hjørner og følgelig kanter (også kalt en enkel sti), avhengig av kilden. Viktige spesialtilfeller inkluderer induserte stier og korteste stier .
nedbrytning av banen
En sti -dekomponering av en graf G er en trenedbrytning hvis underliggende tre er en bane. Bredden er definert på samme måte som for nedbrytning av tre, som en mindre enn størrelsen på den største posen. Den minimale bredde av banen nedbryting av G er den pathwidth av G .
banebredde
Den pathwidth av en graf G er den minste bredde av en bane dekomponering av G . Det kan også defineres i forhold til den gjeng antallet et intervall fullføring av G . Det er alltid mellom båndbredde og treewidth av G . Det er også kjent som intervalltykkelse, toppunktseparasjonsnummer eller nodesøkningsnummer.
anheng
Se blad .
perfekt
1. En perfekt graf er en graf der det kromatiske tallet i alle induserte undergrafer er lik klikkantallet. Den perfekte grafsetningen og den sterke perfekte grafsetningen er to setninger om perfekte grafer, den første viser at komplementene deres også er perfekte, og den siste viser at de er nøyaktig grafene uten merkelige hull eller antihull.
2. En perfekt bestillbar graf er en graf hvis hjørner kan bestilles på en slik måte at en grådig fargealgoritme med denne rekkefølgen optimalt farger hver induserte undergraf. De perfekt bestillbare grafer er en underklasse av de perfekte grafer.
3. En perfekt matching er en matching som metter hvert toppunkt; se samsvar .
4. En perfekt 1-faktorisering er en inndeling av kantene på en graf i perfekte matchninger, slik at hver to matchning danner en hamiltonsyklus.
perifer
1. En perifer syklus eller ikke-separerende syklus er en syklus med høyst en bro.
2. Et perifert toppunkt er et toppunkt hvis eksentrisitet er maksimal. I et tre må dette være et blad.
Petersen
1.   Julius Petersen (1839–1910), dansk grafteoretiker.
2. Petersen-grafen , en 10-toppunkt 15-kant graf som ofte brukes som et moteksempel.
3.   Petersens teori om at hver brofri kubikkgraf har en perfekt matchning.
plan
En plan graf er en graf som har en innebygd i det euklidiske planet. En plangraf er en plan graf som en bestemt innebygging allerede er blitt fikset for. En k -plan graf er en som kan tegnes i planet med maksimalt k kryssinger per kant.
polytree
Et polytree er et orientert tre; ekvivalent, en rettet asyklisk graf hvis underliggende ikke -styrte graf er et tre.
makt
1. En grafeffekt G k for en graf G er en annen graf på det samme toppunktssettet; to hjørner ligger ved siden av i G k når de er i en avstand på høyst k i G . En bladkraft er et nært beslektet konsept, avledet fra et treets kraft ved å ta undergrafen indusert av treets blader.
2.   Strøm graf analyse er en metode for å analysere komplekse nettverk ved å identifisere seg klikker, bicliques og stjerner i nettverket.
3.   Maktlover i gradefordelingene av skalafrie nettverk er et fenomen der antall hjørner av en gitt grad er proporsjonal med graden av graden.
forgjenger
Et toppunkt som kommer foran et gitt toppunkt i en rettet bane .
ordentlig
1. En skikkelig subgraf er en subgraf som fjerner minst ett toppunkt eller en kant i forhold til hele grafen; for endelige grafer er riktige undergrafer aldri isomorfe for hele grafen, men for uendelige grafer kan de være.
2. En riktig farging er en tildeling av farger til hjørnene i en graf (en fargelegging) som tildeler forskjellige farger endepunktene til hver kant; se farge .
3. En riktig intervallgraf eller riktig sirkelbue -graf er en skjæringsgraf for en samling av intervaller eller sirkelbuer (henholdsvis) slik at ingen intervall eller bue inneholder et annet intervall eller en bue. Riktige intervallgrafer kalles også enhetsintervallgrafer (fordi de alltid kan representeres med enhetsintervaller) eller likegyldighetsgrafer.
eiendom
En grafegenskap er noe som kan være sant for noen grafer og falskt for andre, og som bare avhenger av grafstrukturen og ikke av tilfeldig informasjon som etiketter. Grafegenskaper kan tilsvarende beskrives i form av klasser av grafer (grafene som har en gitt egenskap). Mer generelt kan en grafegenskap også være en funksjon av grafer som igjen er uavhengig av tilfeldig informasjon, for eksempel størrelsen, rekkefølgen eller gradsekvensen til en graf; denne mer generelle definisjonen av en eiendom kalles også en invariant av grafen.
pseudoforest
En pseudoforest er en ikke -styrt graf der hver tilkoblede komponent har høyst en syklus, eller en rettet graf der hvert toppunkt har høyst en utgående kant.
pseudograf
En pseudograf er en graf eller multigraf som tillater selvløkker.

Sp

kvasi-linjediagram
En kvasi-linjediagram eller en lokalt topartig graf er en graf der det åpne nabolaget til hvert toppunkt kan deles inn i to klikk. Disse grafene er alltid klofrie og inkluderer linjediagrammer som et spesielt tilfelle . De brukes i strukturteorien til klofrie grafer.
dirren
Et siver er en rettet multigraf, som brukt i kategoriteori . Kantene på en dirren kalles piler.

R

radius
Radiusen til en graf er minimum eksentrisitet for ethvert toppunkt.
Ramanujan
En Ramanujan -graf er en graf hvis spektrale ekspansjon er så stor som mulig. Det vil si at det er en d -regulær graf, slik at den nest største egenverdien til dens tilknytningsmatrise er høyst .
stråle
En stråle, i en uendelig graf, er en uendelig enkel bane med nøyaktig ett endepunkt. De ender av en kurve som er ekvivalens klasser av stråler.
nåbarhet
Evnen til å komme fra et toppunkt til et annet i en graf .
tilgjengelig
Har en bekreftende tilgjengelighet . Et toppunkt y sies å være tilgjengelig fra et toppunkt x hvis det finnes en vei fra x til y .
gjenkjennelig
I konteksten for rekonstruksjonstanken er en grafegenskap gjenkjennelig hvis dens sannhet kan bestemmes ut fra grafikkens dekk. Mange grafegenskaper er kjent for å være gjenkjennelige. Hvis rekonstruksjonen er sann, er alle grafegenskapene gjenkjennelige.
gjenoppbygging
Den rekonstruksjon formodning fastslår at hver enkelt-rettet grafe G er entydig bestemt av dens dekk , en multiset av grafer som dannes ved å fjerne et toppunkt fra G på alle mulige måter. I denne sammenhengen er rekonstruksjon dannelsen av en graf fra dekket.
rektangel
En enkel syklus som består av nøyaktig fire kanter og fire hjørner.
regelmessig
En graf er d -regelmessig når alle dens hjørner har grad d . En vanlig graf er en graf som er d -regelmessig for noen d .
vanlig turnering
En vanlig turnering er en turnering der grad er lik ut-grad for alle hjørner.
omvendt
Se transponering .
rot
1. Et angitt toppunkt i en graf, spesielt i rettet trær og forankrede grafer .
2. Den omvendte operasjonen til en grafeffekt : en k th rot av en graf G er en annen graf på samme toppunkt sett slik at to hjørner er tilstøtende i G hvis og bare hvis de har avstand høyst k i roten.

S

andre bestilling
Den andre ordens logikk for grafer er en form for logikk der variabler kan representere hjørner, kanter, sett med hjørner og (noen ganger) sett med kanter. Denne logikken inkluderer predikater for å teste om et toppunkt og en kant er innfallende, samt om et toppunkt eller en kant tilhører et sett. For å skille seg fra første ordens logikk, der variabler bare kan representere hjørner.
mettet
Se samsvar .
søkernummer
Nodesøkingsnummer er et synonym for banebredde .
selvsløyfe
Synonym for loop .
skille toppunkt
Se artikulasjonspunktet .
separasjonsnummer
Vertex -separasjonsnummer er et synonym for banebredde .
enkel
1. En enkel graf er en graf uten sløyfer og uten flere adjacenser. Det vil si at hver kant forbinder to forskjellige endepunkter, og ingen to kanter har de samme endepunktene. En enkel kant er en kant som ikke er en del av en multipel adjacency. I mange tilfeller antas grafer å være enkle med mindre annet er spesifisert.
2. En enkel bane eller en enkel syklus er en bane eller syklus som ikke har gjentatte hjørner og følgelig ingen gjentatte kanter.
synke
En vask, i en rettet graf, er et toppunkt uten utgående kanter (ut-grad er lik 0).
størrelse
Størrelsen på en graf G er tallet på kantene, | E ( G ) | . Variabelen m brukes ofte for denne mengden. Se også rekkefølge , antall hjørner.
liten verden nettverk
Et litenverdenettverk er en graf der de fleste noder ikke er naboer til hverandre, men de fleste noder kan nås fra hver annen node med et lite antall hopp eller trinn. Nærmere bestemt er et litenverdenettverk definert som en graf der den typiske avstanden L mellom to tilfeldig valgte noder (antall trinn som kreves) vokser proporsjonalt med logaritmen til antall noder N i nettverket
snark
En snark er en enkel, tilkoblet, broløs kubikkgraf med kromatisk indeks lik 4.
kilde
En kilde, i en rettet graf, er et toppunkt uten innkommende kanter (grad er lik 0).
rom
I algebraisk grafteori kan flere vektorrom over det binære feltet være knyttet til en graf. Hver har sett med kanter eller hjørner for sine vektorer, og symmetrisk forskjell av sett som sin vektorsumoperasjon. Den kant plass er det plass for alle sett med kanter, og at toppunktet plass er det plass for alle sett med toppunkter. Den snitt plass er et underrom av kanten plass som har de kappede-sett av grafen som dens elementer. Den syklus plass har Eulerian borrelås-subgraphs som dens elementer.
skiftenøkkel
En skiftenøkkel er en (vanligvis sparsom) graf hvis korteste baneavstand tilnærmet dem i en tett graf eller et annet metrisk mellomrom. Variasjoner inkluderer geometriske nøkkler , grafer hvis hjørner er punkter i et geometrisk rom; trenøkler , spennende trær i en graf hvis avstander er tilnærmet grafavstandene, og grafnøkler, sparsomme undergrafer av en tett graf hvis avstander er omtrentlige til den opprinnelige grafens avstander. En grådig skiftenøkkel er en grafnøkkel som er konstruert av en grådig algoritme, vanligvis en som vurderer alle kanter fra korteste til lengste og beholder de som er nødvendige for å bevare avstanden tilnærming.
spenner
En subgraf strekker seg over når den inkluderer alle hjørnene i den gitte grafen. Viktige saker inkluderer spenning av trær , spenning av undergrafer som er trær, og perfekte matchninger , som spenner over undergrafer som er matchninger. En spennende subgraf kan også kalles en faktor , spesielt (men ikke bare) når den er vanlig.
sparsom
En sparsom graf er en som har få kanter i forhold til antall hjørner. I noen definisjoner bør den samme egenskapen også gjelde for alle undergrafer av den gitte grafen.
spektral
spekter
Spekteret til en graf er samlingen av egenverdier av dens tilknytningsmatrise. Spektralgrafteori er grenen av grafteorien som bruker spektra for å analysere grafer. Se også spektral ekspansjon .
dele
1. En delt graf er en graf hvis hjørner kan deles i en klikk og et uavhengig sett. En beslektet klasse med grafer, dobbeltsplittede grafer, brukes i beviset på den sterke perfekte grafsetningen.
2. En deling av en vilkårlig graf er en inndeling av dens hjørner i to ikke -frittliggende undersett, slik at kantene som strekker seg over dette snittet danner et komplett todelt undergraf. Splittene i en graf kan representeres av en trestruktur som kalles splittet dekomponering . En splitt kalles en sterk splittelse når den ikke krysses av noen annen splittelse. En splitt kalles nontrivial når begge sidene har mer enn ett toppunkt. En graf kalles prime når den ikke har noen ikke -delte splitter.
torget
1. Kvadratet av en graf G er den kurve som kraften G 2 ; i den andre retningen er G kvadratroten til G 2 . Den halve kvadraten til en todelt graf er subgrafen til kvadratet indusert av den ene siden av todelen.
2. En firkant er en plan graf som kan tegnes slik at alle avgrensede flater er 4-sykluser og alle hjørner av grad ≤ 3 tilhører ytre flate.
3. En firkantet rutenettdiagram er en gittergraf som er definert fra punkter i planet med heltallskoordinater forbundet med enhetslengdekanter.
stabil
Et stabilt sett er et synonym for et uavhengig sett .
stjerne
En stjerne er et tre med ett indre toppunkt; tilsvarende er det en komplett todelt graf K 1, n for noen n ≥ 2 . Spesialtilfellet til en stjerne med tre blader kalles en klo.
styrke
Den styrke av en kurve som er det minste forholdet mellom antall kanter som fjernes fra kurven til komponenter laget, over samtlige mulige fjerning; det er analogt med seighet, basert på fjerning av toppunkt.
sterk
1. For sterk tilkobling og sterkt tilkoblede komponenter i dirigerte grafer, se tilkoblet og komponent . En sterk orientering er en orientering som er sterkt forbundet; se orientering .
2. For den sterke perfekte grafsetningen , se perfekt .
3. En sterkt vanlig graf er en vanlig graf der hver to tilstøtende hjørner har samme antall delte naboer og hver to ikke-tilstøtende hjørner har samme antall delte naboer.
4. En kraftig akkordgraf er en akkordgraf der hver jevne syklus med lengde seks eller flere har et merkelig akkord.
5. En sterkt perfekt graf er en graf der hver induserte undergraf har et uavhengig sett som møter alle maksimale klikk. De Meyniel grafene er også kalt "veldig sterkt perfekt grafer" fordi i dem, tilhører hver toppunktet i en slik uavhengig sett.
underskogen
Et underbilde av en skog .
undergraf
En sub-graf av en graf G er en annen kurve som er dannet fra et delsett av vertekser og kanter G . Topppunktsundersettet må inneholde alle endepunkter for kantundersettet, men kan også inneholde flere hjørner. En spennende subgraf er en som inkluderer alle hjørnene i grafen; en indusert subgraf er en som inkluderer alle kantene hvis endepunkter tilhører toppunktundersettet.
undertre
Et undertre er en tilkoblet undergraf av et tre. Noen ganger, for rotete trær, er undertrær definert som en spesiell type tilkoblet undergraf, dannet av alle hjørner og kanter som kan nås fra et valgt toppunkt.
etterfølger
Et toppunkt som kommer etter et gitt toppunkt i en rettet bane .
superkonsentrator
En superkonsentrator er en graf med to angitte og like store undersett av hjørner I og O , slik at for hver to like store undersett S av I og T O eksisterer det en familie av usammenhengende stier som forbinder hvert toppunkt i S med et toppunkt i T . Noen kilder krever i tillegg at en superkonsentrator er en rettet acyklisk graf, med I som kilder og O som synker.
supergraf
En graf dannet ved å legge til hjørner, kanter eller begge deler til en gitt graf. Dersom H er en subgraf av G , og G er en supergraph av H .

T

theta
1. En theta -graf er foreningen av tre internt usammenhengende (enkle) baner som har de samme to distinkte endepunktene.
2. Theta -grafen for en samling punkter i det euklidiske planet er konstruert ved å konstruere et system av kjegler som omgir hvert punkt og legge til en kant per kjegle, til punktet hvis projeksjon på en sentral stråle av kjeglen er minst.
3. Lovász -tallet eller Lovász theta -funksjonen til en graf er en graf invariant relatert til klikketallet og kromatisk tall som kan beregnes i polynomtid ved semidefinitt programmering.
topologisk
1. En topologisk graf er en representasjon av hjørnene og kantene på en graf etter punkter og kurver i planet (ikke nødvendigvis å unngå kryss).
2.   Topologisk grafteori er studiet av grafinnbygginger.
3.   Topologisk sortering er det algoritmiske problemet med å arrangere en rettet asyklisk graf i en topologisk rekkefølge, en toppunktsekvens slik at hver kant går fra et tidligere toppunkt til et senere toppunkt i sekvensen.
helt frakoblet
Synonym for kantløs .
tur
En lukket sti, en tur som starter og slutter ved samme toppunkt og ikke har gjentatte kanter. Euler -turer er turer som bruker alle grafkantene; se Eulerian .
turnering
En turnering er en orientering av en komplett graf; det vil si at det er en rettet graf slik at hver to hjørner er forbundet med nøyaktig en rettet kant (går bare i en av de to retningene mellom de to hjørnene).
sporbar
En sporbar graf er en graf som inneholder en Hamiltonsk bane.
sti
En tur uten gjentatte kanter.
transitive
Har å gjøre med den transitive eiendommen . Den transitive lukkingen av en gitt rettet graf er en graf på det samme toppunktssettet som har en kant fra et toppunkt til et annet når den opprinnelige grafen har en bane som forbinder de samme to toppunktene. En transitiv reduksjon av en graf er en minimal graf som har samme transitive lukking; dirigerte asykliske grafer har en unik transitiv reduksjon. En transitiv orientering er en orientering av en graf som er dens egen transitive lukking; den eksisterer bare for sammenligningsgrafer .
transponere
Den transponere graf av en gitt rettet graf er et diagram som på samme topp-punktene, idet hver kant reversert i retning. Det kan også kalles omvendt eller omvendt av grafen.
tre
1. Et tre er en ikke -styrt graf som er både koblet og asyklisk, eller en rettet graf der det finnes en unik spasertur fra ett toppunkt (roten til treet) til alle gjenværende hjørner.
2. Et k -tre er en graf som dannes ved å lime ( k + 1) -klikker sammen på delte k -klikker. Et tre i vanlig forstand er et 1 -tre i henhold til denne definisjonen.
nedbrytning av tre
En trenedbrytning av en graf G er et tre hvis noder er merket med sett med hjørner av G ; disse settene kalles poser. For hvert toppunkt v må posene som inneholder v indusere et undertre av treet, og for hver kant uv må det finnes en pose som inneholder både u og v . Bredden på et nedbryting av et tre er en mindre enn det maksimale antallet hjørner i noen av posene; den treewidth av G er den minimale bredde av tre dekomponering av G .
trebredde
Den treewidth av en graf G er den minste bredde av et tre dekomponering av G . Det kan også defineres i forhold til den gjeng antallet en korde fullføring av G , i størrelsesorden av en havn av G , eller rekkefølgen av en torne av G .
triangel
En syklus med lengde tre i en graf. En trekantfri graf er en ikke-dirigert graf som ikke har noen trekantundergrupper.
Turán
1.   Pál Turán
2. En Turán -graf er en balansert komplett flerpartsgraf.
3.   Turáns teorem sier at Turán-grafer har maksimalt antall kanter blant alle klikkfrie grafer i en gitt rekkefølge.
4.   Turans mursteinfabrikkproblem ber om minimum antall kryssinger i en tegning av en komplett topartig graf.

U

ikke styrt
En ikke -styrt graf er en graf der de to endepunktene i hver kant ikke skilles fra hverandre. Se også regissert og blandet . I en blandet graf er en urettet kant igjen en der endepunktene ikke skilles fra hverandre.
uniform
En hypergraph er k -uniform når alle sine kanter har k endepunkter, og ensartet når det er k -uniform for noen k . For eksempel er vanlige grafer det samme som 2 -ensartede hypergrafer.
universell
1. En universell graf er en graf som inneholder som grafer alle grafer i en gitt familie av grafer, eller alle grafer av en gitt størrelse eller rekkefølge innenfor en gitt familie av grafer.
2. Et universelt toppunkt (også kalt toppunkt eller dominerende toppunkt) er et toppunkt som ligger ved siden av hvert annet toppunkt i grafen. For eksempel har hjulgrafer og tilkoblede terskeldiagrammer alltid et universelt toppunkt.
3. I grafikkens logikk kan et toppunkt som er universelt kvantifisert i en formel kalles et universelt toppunkt for den formelen.
uvektet graf
En graf hvis hjørner og kanter s ikke har blitt tildelt vekt s ; det motsatte av en vektet graf .

V

V
Se toppunktsett .
valens
Synonym for grad .
toppunkt
Et toppunkt (flertallskanter) er (sammen med kanter) en av de to grunnleggende enhetene som grafer er konstruert av. Hjørner av grafer anses ofte å være atomobjekter, uten indre struktur.
toppunktskutt
skillesett
Et sett med hjørner hvis fjerning kobler fra grafen . Et ett-vertex-kutt kalles et artikulasjonspunkt eller cut-vertex .
toppunkt sett
Settet med hjørner av en gitt graf G , noen ganger betegnet med V ( G ) .
hjørner
Se toppunkt .
Vizing
1.   Vadim G. Vizing
2.   Vizing's teorem om at den kromatiske indeksen høyst er én mer enn maksgraden .
3.   Vizing's formodning om dominansantallet for kartesiske produkter av grafer.
volum
Summen av grader av et sett med hjørner.

W

W
Bokstaven W brukes i notasjon for hjulgrafer og vindmøllediagrammer . Notasjonen er ikke standardisert.
Wagner
1.   Klaus Wagner
2. Wagner-grafen , en Möbius-stige med åtte vertex.
3.   Wagners teorem som karakteriserer plane grafer etter deres forbudte mindreårige.
4. Wagners teorem som kjennetegner K 5 -minorfrie grafer.
En tur er en endelig eller uendelig sekvens av kanter som slutter seg til en sekvens av hjørner . Turer kalles også noen ganger kjeder . En spasertur er åpen hvis dens første og siste toppunkt er forskjellige, og lukket hvis de gjentas.
svakt forbundet
En dirigert graf kalles svakt tilkoblet hvis erstatning av alle de kantede kantene med ikke -styrte kanter gir en tilkoblet (ikke -styrt) graf.
vekt
En numerisk verdi, tilordnet som en etikett til et toppunkt eller kant av en graf. Vekten til en undergraf er summen av vekten av hjørnene eller kantene i den undergrafen.
vektet graf
En graf som topp-punkt eller kant s er tilordnet vekt s ; mer spesifikt, en toppunktvektet graf har vekter på sine hjørner og en kantvektet graf har vekter på kantene.
godt farget
En godt farget graf er en graf som alle de grådige fargestoffene bruker samme antall farger.
godt dekket
En godt dekket graf er en graf som alle har sine maksimale uavhengige sett med samme størrelse.
hjul
En hjulgraf er en graf dannet ved å legge et universelt toppunkt til en enkel syklus.
bredde
1. Et synonym for degenerasjon .
2. For andre grafinvarianter kjent som bredde, se båndbredde , grenbredde , klikkbredde , banebredde og trebredde .
3. Bredden på en trenedbrytning eller nedbrytning av stier er en mindre enn maksimal størrelse på en av posene, og kan brukes til å definere trebredde og stibredde.
4. Bredden på en rettet asyklisk graf er den maksimale kardinaliteten til et antikjede.
vindmølle
En vindmøllediagram er foreningen av en samling klikker, alle i samme rekkefølge som hverandre, med ett delt toppunkt som tilhører alle klikkene og alle andre hjørner og kanter som er forskjellige.

Se også

Referanser