Ordliste over grafteori - Glossary of graph theory

Dette er en ordliste over grafteori . Grafteori er studiet af grafer , systemer af noder eller hjørner forbundet parvis med linjer eller kanter .

Symboler

Firkantede beslag []
G [ S ] er den inducerede undergrafen af en graf G for vinkelspids delmængde S .
Prime symbol '
Den primære symbol bruges ofte til at modificere notation for graf invarianter, så det gælder for linje graf i stedet for den givne graf. For eksempel er α ( G ) uafhængighedstallet for en graf; α ′ ( G ) er grafens matchende nummer, der er lig med uafhængighedstallet for dets linjediagram. På samme måde er χ ( G ) det kromatiske tal i en graf; χ  ′ ( G ) er grafens kromatiske indeks, der er lig med det kromatiske tal for dets linjediagram.

EN

absorberende
Et absorberende sæt af en rettet graf er et sæt hjørner, således at der for enhver toppunkt er en kant fra mod et toppunkt af .
achromatisk
Det grafiske akromatiske tal er det maksimale antal farver i en komplet farve.
acyklisk
1. En graf er acyklisk, hvis den ikke har nogen cyklusser. En ikke -styret acyklisk graf er det samme som en skov . Dirigerede acykliske grafer kaldes sjældnere acyklisk dirigerede grafer.
2. En acyklisk farvning af en ikke -styret graf er en korrekt farvning, hvor hver anden farveklasse fremkalder en skov.
tilstødelsesmatrix
Den nabomatrix af en graf er en matrix, hvis rækker og søjler er begge indekseret af knudepunkter af grafen, med en en i cellen for række i og søjle j når toppunkter i og j er tilstødende, og en ellers nul.
tilstødende
1. Forholdet mellem to hjørner, der begge er endepunkter i samme kant.
2. Forholdet mellem to forskellige kanter, der deler et endepunkt.
α
For en graf G er α ( G ) (ved hjælp af det græske bogstav alpha) dens uafhængighedsnummer (se uafhængigt ), og α ′ ( G ) er dets matchende nummer (se matching ).
skiftevis
I en graf med en matchning er en vekslende sti en sti, hvis kanter skifter mellem matchede og umatchede kanter. En vekslende cyklus er på samme måde en cyklus, hvis kanter skifter mellem matchede og umatchede kanter. En forstørrelsessti er en vekslende sti, der starter og slutter ved umættede hjørner. En større matchning kan findes som den symmetriske forskel på matchningen og forstørrelsesbanen; en matchning er maksimal, hvis og kun hvis den ikke har nogen forstørrelsessti.
antikæde
I en rettet acyklisk graf , en delmængde S af hjørner, der er parvise uforlignelige, dvs. for enhver i S , er der ingen rettet vej fra x til y eller fra y til x . Inspireret af forestillingen om antikæder i delvist bestilte sæt .
anti-kant
Synonym for ikke-kant , et par ikke-tilstødende hjørner.
anti-trekant
Et uafhængigt sæt med tre vertex, komplementet til en trekant.
spids
1. En spidsgraf er en graf, hvor et toppunkt kan fjernes og efterlader et plant undergraf. Det fjernede toppunkt kaldes spidsen. En k -apex -graf er en graf, der kan laves plan ved fjernelse af k -hjørner.
2. Synonym for universal toppunkt , et toppunkt støder op til alle andre hjørner.
arborescens
Synonym for et rodfæstet og styret træ; se træ .
bue
Se kant .
pil
En ordnet par af knuder , såsom en kant i en orienteret graf . En pil ( x , y ) har en hale x , et hoved y og en retning fra x til y ; y siges at være den direkte efterfølger til x og x den direkte forgænger til y . Pilen ( y , x ) er pilens omvendte pil ( x , y ) .
artikulationspunkt
Et toppunkt i en tilsluttet graf, hvis fjernelse ville afbryde grafen.
-ary
Et k -ary træ er et rodfæstet træ, hvor hvert indre toppunkt ikke har mere end k børn. Et 1-ary træ er bare en sti. Et 2-ary træ kaldes også et binært træ , selvom dette udtryk mere korrekt refererer til 2-ary træer, hvor børnene i hver knude udmærker sig som venstre eller højre børn (med højst en af ​​hver type). Et k -ary træ siges at være komplet, hvis hvert indre toppunkt har præcis k børn.
forstærkning
En særlig type skiftevej; se skiftevis .
automorfisme
En grafautomorfisme er en symmetri af en graf, en isomorfisme fra grafen til sig selv.

B

taske
Et af sætene med hjørner i en trænedbrydning .
afbalanceret
En to- eller flerpartsgraf er afbalanceret, hvis hver to delmængder af dens toppunktpartition har størrelser inden for hinanden.
båndbredde
Den båndbredde af en graf G er minimum, frem for alle rækkefølger af knudepunkter af G , af længden af den længste kant (antallet af trin i rækkefølgen mellem dens to endepunkter). Det er også en mindre end størrelsen af ​​den maksimale klik i et korrekt interval afslutning af G , valgt for at minimere klikstørrelsen.
biclique
Synonym for komplet bipartit graf eller komplet bipartit subgraf; se komplet .
tilsluttet
Normalt et synonym for 2 -vertex-forbundet , men inkluderer undertiden K 2, selvom det ikke er 2-forbundet. Se tilsluttet ; for komponenter , der er forbundet med hinanden , se komponent .
bindende nummer
Det mindste mulige forhold mellem antallet af naboer i en ordentlig delmængde af hjørner og størrelsen på undersættet.
todelt
En todelt graf er en graf, hvis hjørner kan opdeles i to usammenhængende sæt, således at hjørnerne i et sæt ikke er forbundet med hinanden, men kan forbindes med hjørner i det andet sæt. Sagt på en anden måde, en todelt graf er en graf uden ulige cyklusser; tilsvarende er det en graf, der kan være korrekt farvet med to farver. Bipartit -grafer skrives ofte G = ( U , V , E ), hvor U og V er undersæt af hjørner af hver farve. Men medmindre grafen er forbundet, har den muligvis ikke en unik 2-farve.
biregular
En biregulær graf er en todelt graf, hvor der kun er to forskellige toppunktsgrader, en for hvert sæt af toppunktets topartition.
blok
1. En blok i en graf G er en maksimal subgraf, som enten er et isoleret toppunkt, en brokant eller et 2-forbundet subgraf. Hvis en blok er 2-forbundet, tilhører hvert par hjørner i den en fælles cyklus. Hver kant af en graf hører til i præcis en blok.
2. Blokgrafen for en graf G er en anden graf, hvis hjørner er blokkene af G , med en kant, der forbinder to hjørner, når de tilsvarende blokke deler et artikulationspunkt; det vil sige, det er skæringspunktet graf af blokke af G . Blokgrafen for enhver graf er en skov .
3. Blokken-cut (eller blok-skærepunkt) graf af en graf G er en todelt graf, hvor man partite sæt består af cut-knudepunkter af G , og den anden har et toppunkt for hver blok af G . Når G er forbundet, er dens blok-cutpoint-graf et træ.
4. En blok graf (også kaldet en klike træ hvis tilsluttet, og undertiden fejlagtigt kaldet en Husimi træ) er en graf, hvor alle blokke er komplet graf. En skov er en blokgraf; så især er blokgrafen for enhver graf en blokgraf, og hver blokgraf kan konstrueres som blokgrafen for en graf.
bånd
Et minimalt snit-sæt : et sæt kanter, hvis fjernelse afbryder grafen, som ingen ordentlig delmængde har den samme egenskab for.
Bestil
1. En bog , boggraf eller trekantet bog er en komplet trepartsgraf K 1,1, n ; en samling af n trekanter forbundet ved en delt kant.
2. En anden graftype, også kaldet en bog eller en firkantet bog, er en samling af 4 -cykler, der er forbundet ved en delt kant; det kartesiske produkt af en stjerne med en kant.
3. En bogindlejring er en indlejring af en graf på en topologisk bog, et rum dannet ved at forbinde en samling af halvplaner langs en delt linje. Normalt skal indlejringens hjørner være på linjen, som kaldes indlejringens rygsøjle, og indlejringens kanter skal ligge inden for et enkelt halvplan, en af ​​siderne i bogen.
bramble
En bramble er en samling af indbyrdes rørende forbundne undergrafer, hvor to undergrafer rører, hvis de deler et toppunkt eller hver indeholder et endepunkt på en kant. Rækkefølgen på et bramble er den mindste størrelse af et sæt hjørner, der har et ikke -frit kryds med alle subgraferne. Trebredden af ​​en graf er den maksimale rækkefølge for enhver af dens brambles.
forgrening
En gren-nedbrydning af G er en hierarkisk klyngedannelse af kanterne af G , repræsenteret ved en urodede binært træ med sine blade mærket med kanterne af G . Bredden af ​​en grennedbrydning er maksimum, over kanterne e af dette binære træ, af antallet af delte hjørner mellem undergraferne bestemt af kanterne af G i de to undertræer adskilt af e . Den branchwidth af G er den mindste bredde af enhver gren-nedbrydning af G .
grenbredde
Se forgrening .
bro
1. En bro , landtange eller skærkant er en kant, hvis fjernelse ville afbryde grafen. En brofri graf er en, der ikke har broer; tilsvarende en 2-kant-forbundet graf.
2. Især i forbindelse med planaritetstest er en cyklusbro en maksimal subgraf, der er adskilt fra cyklussen, og hvor hver to kanter tilhører en sti, der er internt adskilt fra cyklussen. En akkord er en bro med en kant. En perifer cyklus er en cyklus med højst en bro; det skal være et ansigt i enhver plan indlejring af grafen.
3. En bro i en cyklus kan også betyde en sti, der forbinder to hjørner af en cyklus, men er kortere end en af ​​stierne i cyklussen, der forbinder de samme to hjørner. En brobro er en graf, hvor hver cyklus med fire eller flere hjørner har en bro.
brofri
En brofri graf er en graf, der ikke har brokanter; det vil sige en 2-kant-tilsluttet graf .
sommerfugl
1. Sommerfuglgrafen har fem hjørner og seks kanter; den er dannet af to trekanter, der deler et toppunkt.
2. Sommerfuglenetværket er en graf, der bruges som netværksarkitektur i distribueret databehandling, tæt forbundet med de kubeforbundne cyklusser .

C

C
C n er et n -vertex cyklus graf ; se cyklus .
kaktus
En kaktus graf , kaktus træ, kaktus, eller Husimi træ er en forbunden graf hvori hver kant hører til højst én cyklus. Dens blokke er cyklusser eller enkelte kanter. Hvis derudover hvert toppunkt tilhører højst to blokke, så kaldes det en julekaktus.
bur
Et bur er en almindelig graf med den mindst mulige rækkefølge for dets omkreds.
kanonisk
kanonisering
En kanonisk form for en graf er en invariant sådan, at to grafer har lige invarianter, hvis og kun hvis de er isomorfe. Kanoniske former kan også kaldes kanoniske invarianter eller komplette invarianter og er undertiden kun defineret for graferne inden for en bestemt familie af grafer. Grafkanonisering er processen med at beregne en kanonisk form.
kort
En graf dannet ud fra en given graf ved at slette et toppunkt, især i forbindelse med rekonstruktionstanken . Se også dæk , multisættet af alle kort i en graf.
udskæringsbredde
Skæringsbredde er en forestilling om grafbredde, der er analog med grenbredde, men ved hjælp af hierarkiske klynger af hjørner i stedet for hierarkiske klynger af kanter.
larve
Et larvetræ eller larve er et træ, hvor de interne knuder fremkalder en sti.
centrum
Den centrum af en graf er det sæt af knudepunkter af minimal excentricitet .
kæde
1. Synonym for gåtur .
2. Ved anvendelse af metoder fra algebraisk topologi til grafer, et element i et kædekompleks , nemlig et sæt hjørner eller et sæt kanter.
Cheeger konstant
Se udvidelse .
kirsebær
En kirsebær er en sti på tre hjørner.
χ
χ ( G ) (ved hjælp af det græske bogstav chi) er det kromatiske tal for G og χ  ′ ( G ) er dets kromatiske indeks; se kromatisk og farvelægning .
barn
I et rodfæstet træ er et barn af et toppunkt v en nabo til v langs en udgående kant, et, der ledes væk fra roden.
akkord
akkord
1. En akkord af en cyklus er en kant, der ikke tilhører cyklussen, for hvilken begge endepunkter tilhører cyklussen.
2. En akkordgraf er en graf, hvor hver cyklus med fire eller flere hjørner har en akkord, så de eneste inducerede cyklusser er trekanter.
3. En stærkt akkordgraf er en akkordgraf, hvor hver cyklus med længde seks eller flere har en ulige akkord.
4. En akkordbipartitgraf er ikke akkordal (medmindre det er en skov); det er en todelt graf, hvor hver cyklus med seks eller flere hjørner har en akkord, så de eneste inducerede cyklusser er 4-cyklusser.
5. En cirkelakkord er et linjesegment, der forbinder to punkter på cirklen; den krydset graf af en samling akkorder kaldes en cirkel graf .
kromatisk
At have med farve at gøre; se farve . Kromatisk grafteori er teorien om graffarvning. Den kromatiske tal χ ( G ) er det mindste antal af farver, der er nødvendige i en ordentlig farvning af G . χ  ( G ) er den kromatiske indeks af G , antallet af farver, der er nødvendige i en ordentlig minimum kant farvning af G .
valgbar
valgbarhed
En graf er k -choosable hvis den har en liste farve , når hvert hjørne har en liste over k tilgængelige farver. Valgbarheden af ​​grafen er den mindste k, som den er k -valgbar.
cirkel
En cirkeldiagram er skæringsgrafen for akkorder i en cirkel.
kredsløb
Et kredsløb kan henvise til en lukket sti eller et element af cyklus rum (et Eulerske spænder undergraf). Den kredsløb rang af en graf er dimensionen af sin cyklus plads.
omkreds
Den omkreds af en graf er længden af dens længste simpel cyklus. Grafen er Hamiltonsk, hvis og kun hvis dens omkreds er lig med dens rækkefølge.
klasse
1. En klasse af grafer eller en familie af grafer er en (normalt uendelig) samling af grafer, ofte defineret som graferne, der har en bestemt egenskab. Ordet "klasse" bruges i stedet for "sæt", fordi medmindre særlige begrænsninger foretages (f.eks. At begrænse de hjørner, der skal trækkes fra et bestemt sæt, og definere kanter til at være sæt af to hjørner), er grafer normalt ikke sæt når formaliseret ved hjælp af sætteori.
2. En farveklasse for en farvet graf er sættet med hjørner eller kanter med en bestemt farve.
3. I forbindelse med Vizingings sætning , på kantfarvning af simple grafer, siges en graf at være af klasse et, hvis dens kromatiske indeks er lig med sin maksimale grad, og klasse to, hvis dets kromatiske indeks er lig plus en grad. Ifølge Vizinges sætning er alle enkle grafer enten i klasse et eller klasse to.
klo
En klo er et træ med et indre toppunkt og tre blade, eller tilsvarende den komplette topartsgraf K 1,3 . En klo-fri graf er en graf, der ikke har en induceret subgraf, der er en klo.
klik
En klik er et sæt indbyrdes tilstødende hjørner (eller det komplette undergraf fremkaldt af dette sæt). Nogle gange er en klik defineret som et maksimalt sæt af indbyrdes tilstødende hjørner (eller maksimal komplet subgraf), en der ikke er en del af et større sådant sæt (eller undergraf). En k -clique er en klik af rækkefølge k . Den klike nummer κ ( G ) af en graf G er rækkefølgen af dens største klike. En klikgraf er en skæringsgraf med maksimale klik . Se også biclique , en komplet todelt subgraf.
klik træ
Et synonym for en blokgraf .
klikbredde
Den klike bredde af en graf G er det mindste antal af distinkte markører nødvendige for at konstruere G ved operationer, der skaber en mærket toppunkt, danner den disjunkte forening af to mærkede grafer, tilføje en kant forbinder alle par af knuder med givne etiketter, og ometikettering alle hjørner med en given etiket. Graferne med klikbredde højst 2 er præcis katalogerne .
lukket
1. Et lukket kvarter er et, der omfatter dets centrale toppunkt; se kvarter .
2. En lukket gåtur er en, der starter og slutter ved det samme toppunkt; se gåtur .
3. En graf lukkes midlertidigt, hvis den er lig med sin egen transitive lukning; se transitive .
4. En grafegenskab lukkes under en vis handling på grafer, hvis resultatet af argumentet eller argumenterne til operationen har egenskaben. For eksempel lukkes arvelige egenskaber under inducerede subgrafer; monotone egenskaber lukkes under undergrafer; og mindre lukkede ejendomme lukkes under mindreårige.
lukning
1. For transitiv lukning af en rettet graf, se transitiv .
2. En lukning af en rettet graf er et sæt hjørner, der ikke har udgående kanter til hjørner uden for lukningen. For eksempel er en vask en en-vertex lukning. Den lukningen Problemet er problemet med at finde en lukning af minimum eller maksimum vægt.
med-
Dette præfiks har forskellige betydninger, der normalt involverer komplementgrafer . For eksempel er en cograph en graf fremstillet af operationer, der inkluderer komplementering; en cocoloring er en farve, hvor hvert toppunkt inducerer enten et uafhængigt sæt (som ved korrekt farve) eller en klik (som i en farve af komplementet).
farve
farvelægning
1. En graffarvning er en mærkning af en grafs hjørner ved hjælp af elementer fra et givent sæt farver, eller tilsvarende en opdeling af hjørnerne i undersæt, kaldet "farveklasser", som hver er forbundet med en af ​​farverne.
2. Nogle forfattere bruger "farve", uden kvalifikation, til at betyde en ordentlig farve, en der tildeler forskellige farver til slutpunkterne på hver kant. I graffarvning er målet at finde en ordentlig farve, der bruger så få farver som muligt; for eksempel er topartede grafer de grafer, der har farvninger med kun to farver, og de fire farvesætninger angiver, at hver plan graf maksimalt kan farves med fire farver. En graf siges at være k -farvet, hvis den er (korrekt) farvet med k -farver, og k -farverbar eller k -kromatisk, hvis dette er muligt.
3. Mange variationer af farvning er blevet undersøgt, herunder kantfarvning (farvningskanter, så der ikke er to kanter med det samme endepunkt, der deler en farve), listefarvning (korrekt farve med hvert toppunkt begrænset til en delmængde af de tilgængelige farver), acyklisk farvning (hver 2-farvet undergraf er acyklisk), medfarvning (hver farveklasse fremkalder et uafhængigt sæt eller en klik), komplet farve (hver anden farveklasse deler en kant) og totalfarvning (både kanter og hjørner er farvet).
4. Farvenummeret på en graf er et plus degenerationen . Det er såkaldt, fordi anvendelse af en grådig farvelgoritme til en degenerering, der beordrer grafen, højst bruger så mange farver.
sammenlignelighed
En uorienteret graf er en sammenlignelighedsgraf, hvis dens hjørner er elementerne i et delvist ordnet sæt, og to hjørner er tilstødende, når de er sammenlignelige i delordenen. Tilsvarende er en sammenlignelighedsgraf en graf, der har en transitiv orientering. Mange andre klasser af grafer kan defineres som sammenlignelighedsgrafer for særlige typer af delvis rækkefølge.
komplement
Den komplement graf af en simpel graf G er en anden graf på samme toppunkt sæt som G , med en kant for hver to knudepunkter, der ikke er tilgrænsende i G .
komplet
1. En komplet graf er en, hvor hver to hjørner er tilstødende: alle kanter, der kunne eksistere, er til stede. En komplet graf med n hjørner er ofte betegnet K n . En komplet topartsgraf er en, hvor hver to hjørner på modsatte sider af skillevæggen er tilstødende. En komplet topartsgraf med et hjørne på den ene side af skillevæggen og b -hjørner på den anden side er ofte betegnet K a , b . Den samme terminologi og notation er også blevet udvidet til at fuldføre flerpartsgrafer , grafer, hvor hjørnerne er opdelt i mere end to undersæt, og hvert par hjørner i forskellige undergrupper er tilstødende; hvis antallet af knuder i undergrupperne er en , b , c , ... så denne graf er betegnet K a , b , c , ... .
2. En færdiggørelse af en given graf er en supergraf, der har en eller anden ønsket egenskab. For eksempel er en akkordafslutning et supergraf, der er en akkordgraf.
3. En komplet matchning er et synonym for en perfekt matchning ; se matchning .
4. En komplet farve er en korrekt farvning, hvor hvert par af farver bruges til slutpunkterne på mindst en kant. Hver farvning med et minimum antal farver er komplet, men der kan eksistere komplette farvninger med større antal farver. Det grafiske akromatiske tal er det maksimale antal farver i en komplet farve.
5. En komplet invariant af en graf er et synonym for en kanonisk form, en invariant, der har forskellige værdier for ikke-isomorfe grafer.
komponent
En tilsluttet komponent i en graf er en maksimalt forbundet subgraf. Udtrykket bruges også til maksimale undergrafer eller delmængder af en grafs hjørner, der har en vis højere tilslutningsorden, herunder bikoblede komponenter , trikoblede komponenter og stærkt forbundne komponenter .
kondensation
Den kondensering af en orienteret graf G er en orienteret acyklisk graf med en vinkelspids for hver stærkt forbundet komponent i G , og en kant forbinder par af komponenter, der indeholder de to endepunkter af mindst en kant i G .
kegle
En graf, der indeholder et universelt toppunkt .
forbinde
Årsag til at være tilsluttet .
forbundet
En tilsluttet graf er en, hvor hvert par hjørner udgør slutpunkterne for en sti. Højere former for tilslutning omfatter stærk forbindelse i målrettede grafer (for hver to hjørner er der stier fra den ene til den anden i begge retninger), k -vertex -tilsluttede grafer (fjernelse af færre end k -hjørner kan ikke afbryde grafen) og k -kant -tilsluttede grafer (fjernelse af færre end k kanter kan ikke afbryde grafen).
tale
Den omvendte graf er et synonym for transponeringsgrafen; se gennemførelse .
kerne
1. En k -core er den inducerede subgraf dannet ved at fjerne alle hjørner med en grad mindre end k , og alle hjørner, hvis grad bliver mindre end k efter tidligere fjernelser. Se degeneration .
2. En kerne er en graf G, så enhver grafhomomorfisme fra G til sig selv er en isomorfisme.
3. Kernen i en graf G er en minimal graf H, således at der findes homomorfismer fra G til H og omvendt. H er unik op til isomorfisme. Det kan repræsenteres som en induceret delgraf af G og er en kerne i den forstand, at alle dets selvhomomorfismer er isomorfier.
4. I teorien om grafmatchninger er kernen i en graf et aspekt af dens Dulmage – Mendelsohn -nedbrydning , dannet som foreningen af ​​alle maksimale matchninger.
cotree
1. Komplementet til et spændende træ .
2. En rodfæstet træstruktur, der bruges til at beskrive en cograph , hvor hvert cograph -toppunkt er et blad af træet, hver interne knude på træet er mærket med 0 eller 1, og to cograph -hjørner er tilstødende, hvis og kun hvis deres laveste fælles forfader i træet er mærket 1.
dække over
Et toppunktdæksel er et sæt hjørner, der rammer hver kant i en graf. Et kantdæksel er et sæt kanter, der rammer hvert toppunkt i en graf. Et sæt undergrafer af en graf dækker denne graf, hvis dens forening -taget toppunkt- og kantmæssigt-er lig med grafen.
kritisk
En kritisk graf for en given egenskab er en graf, der har egenskaben, men sådan at hver subgraf, der dannes ved at slette et enkelt toppunkt, ikke har egenskaben. For eksempel er en faktor-kritisk graf en, der har en perfekt matchning (en 1-faktor) for hver vertex-sletning, men (fordi den har et ulige antal hjørner) ikke har nogen perfekt matching i sig selv. Sammenlign hypo- , der bruges til grafer, der ikke har en egenskab, men som hver enkelt-toppunkts sletning gør.
terning
kubisk
1.   Terningediagram , otte-toppunktsgrafen for hjørnerne og kanterne på en terning.
2.   Hypercube-graf , en højere dimensionel generalisering af terningediagrammet.
3.   Foldet terningediagram , dannet af en hyperkube ved at tilføje en matchende forbinder modstående hjørner.
4.   Halveret terningediagram , den halve kvadrat af en hyperkubegraf.
5.   Delvis terning , en afstandsbevarende subgraf af en hyperkube.
6. Terningen i en graf G er grafeffekten G 3 .
7.   Kubisk graf , et andet navn for en 3 -regelmæssig graf, en hvor hver toppunkt har tre indfaldende kanter.
8.   Cube-connected cycles , en kubisk graf dannet ved at udskifte hvert toppunkt i en hypercube med en cyklus.
skære
cut-set
Et snit er en opdeling af hjørnerne i en graf i to delmængder eller sættet (også kendt som et snitsæt) af kanter, der spænder over en sådan partition, hvis dette sæt ikke er tomt. Det siges, at en kant spænder over partitionen, hvis den har endepunkter i begge delmængder. Således fjerner fjernelsen af ​​et snitsæt fra en tilsluttet graf det.
skærepunkt
Se artikulationspunkt .
skære plads
Den afskårne plads af en graf er en GF (2) - vektorrum med den cut-sæt s af grafen som dens elementer og symmetrisk forskel i sæt som sin vektor tilsætning drift.
cyklus
En cyklus kan enten referere til en lukket gåtur (også kaldet en tur ) eller mere specifikt til en lukket gåtur uden gentagne hjørner og følgelig kanter (også kaldet en simpel cyklus). I begge tilfælde anses valget af første toppunkt normalt for uvæsentligt: cykliske permutationer af turen producerer den samme cyklus. Vigtige specielle tilfælde af cyklusser inkluderer hamiltonske cyklusser , inducerede cyklusser , perifere cyklusser og den korteste cyklus, som definerer omkredsen af en graf. En k -cyklus er en cyklus med længden k ; for eksempel er en 2 -cyklus en digon og en 3 -cykel er en trekant. En cyklusgraf er en graf, der i sig selv er en simpel cyklus; en cyklusgraf med n hjørner betegnes almindeligvis C n . Den cyklus rum er et vektorrum genereret ved enkle cykler i en graf.

D

DAG
Forkortelse for rettet acyklisk graf , en rettet graf uden nogen rettede cyklusser.
dæk
Multisættet af grafer dannet ud fra en enkelt graf G ved at slette et enkelt toppunkt på alle mulige måder, især i forbindelse med rekonstruktionstanken . Et kantdæk dannes på samme måde ved at slette en enkelt kant på alle mulige måder. Graferne i et kort kaldes også kort . Se også kritiske (grafer, der har en egenskab, der ikke er indeholdt af noget kort) og hypo- (grafer, der ikke har en egenskab, der er indeholdt af alle kort).
nedbrydning
Se træ nedbrydning , sti nedbrydning eller filial-nedbrydning .
degenerere
degeneration
En k -degenerate graf er en ikke-orienteret graf hvor hver induceret undergraf har minimum højst k . Den degenerering af en graf er den mindste k , for hvilket det er k -degenerate. En degenerationsordre er en ordning af hjørnerne således, at hvert toppunkt har minimumsgrad i den inducerede subgraf af det og alle senere hjørner; i en degenerering af en k -genereret graf har hvert toppunkt højst k senere naboer. Degeneration er også kendt som k -core -tallet, bredden og sammenkoblingen, og et plus degenerationen kaldes også farvelægningsnummeret eller Szekeres – Wilf -nummeret. k -genererede grafer er også blevet kaldt k -induktive grafer.
grad
1. Graden af et toppunkt i en graf er dets antal indfaldende kanter. Graden af ​​en graf G (eller dens maksimale grad) er maksimum for graderne af dens hjørner, ofte betegnet Δ ( G ) ; minimumsgraden af G er minimum af dens toppunktsgrader, ofte betegnet δ ( G ) . Grad kaldes undertiden valens ; graden af v i G kan betegnes d G ( v ) , d ( G ) eller deg ( v ) . Den samlede grad er summen af ​​graderne af alle hjørner; ved håndrystende lemma er det et lige tal. Den grad sekvens er en samling af grader af alle knuder, i sorteret rækkefølge fra største til mindste. I en rettet graf kan man skelne mellem grad (antal indgående kanter) og ud-grad (antal udgående kanter).
2. Graden homomorfisme i et diagram er et synonym for dets Hadwiger -nummer , rækkefølgen af ​​den største clique -minor.
Δ, δ
Δ ( G ) (ved hjælp af det græske bogstav delta) er den maksimale grad af et toppunkt i G , og δ ( G ) er minimumsgraden; se grad .
massefylde
I en graf over n -noder er densiteten forholdet mellem antallet af kanter på grafen og antallet af kanter i en komplet graf på n -noder. Se tæt graf .
dybde
Dybden af ​​en knude i et rodfæstet træ er antallet af kanter i stien fra roden til knuden. For eksempel er rodens dybde 0 og dybden af ​​en af ​​dens tilstødende noder er 1. Det er niveauet for en knude minus en. Bemærk dog, at nogle forfattere i stedet bruger dybde som et synonym for niveauet for en knude.
diameter
Diameteren på en tilsluttet graf er maksimumlængden af ​​en korteste vej . Det vil sige, at det er maksimum for afstandene mellem par af hjørner i grafen. Hvis grafen har vægte på sine kanter, måler dens vægtede diameter sti længde med summen af ​​kantvægte langs en sti, mens den uvægtede diameter måler sti længde med antallet af kanter. For frakoblede grafer varierer definitionerne: Diameteren kan defineres som uendelig eller som den største diameter af en tilsluttet komponent, eller den kan være udefineret.
diamant
Den diamant graf er en ikke-orienteret graf med fire knudepunkter og fem kanter.
tilsluttet
Stærk ly tilsluttet . (For ikke at forveksle med afbrudt )
digon
En digon er en simpel cyklus med længde to i en rettet graf eller en multigraf. Digoner kan ikke forekomme i enkle, uorienterede grafer, da de kræver gentagelse af den samme kant to gange, hvilket er i strid med definitionen af simple .
digraph
Synonym for rettet graf .
dipat
Se rettet vej .
direkte forgænger
Halen af ​​en rettet kant, hvis hoved er det givne toppunkt.
direkte efterfølger
Hovedet på en rettet kant, hvis hale er det givne toppunkt.
instrueret
En rettet graf er en, hvor kanterne har en særskilt retning, fra et toppunkt til et andet. I en blandet graf er en rettet kant igen en, der har en særskilt retning; rettede kanter kan også kaldes buer eller pile.
rettet bue
Se pil .
rettet kant
Se pil .
rettet linje
Se pil .
rettet vej
En sti , ved hvilken alle kant s har den samme retning . Hvis en rettet vej fører fra toppunkt x til toppunkt y , er x en forgænger for y , y er en efterfølger af x , og y siges at kunne nås fra x .
retning
1. Det asymmetriske forhold mellem to tilstødende hjørner i en graf , repræsenteret som en pil .
2. Det asymmetriske forhold mellem to hjørner i en rettet sti .
koble fra
Årsag til at blive afbrudt .
afbrudt
Ikke tilsluttet .
usammenhængende
1. To undergrafer er kantdifferentierede, hvis de ikke deler kanter, og toppunktsforbindelse, hvis de ikke deler hjørner.
2. Den usammenhængende forening af to eller flere grafer er en graf, hvis toppunkt og kanter er de sammenføjede foreninger i de tilsvarende sæt.
afstand
Den afstand mellem to knuder i en graf er længden af den korteste vej, der har de to toppunkter som sine endepunkter.
domatisk
En domatisk partition af en graf er en opdeling af hjørnerne i dominerende sæt. Den domatic antal af grafen er det maksimale antal dominerende sæt på en sådan skillevæg.
dominerende
Et dominerende sæt er et sæt hjørner, der omfatter eller støder op til hvert toppunkt i grafen; ikke at forveksle med et toppunktdæksel, et toppunktssæt, der rammer alle kanter i grafen. Vigtige særlige typer dominerende sæt inkluderer uafhængige dominerende sæt (dominerende sæt, der også er uafhængige sæt) og forbundne dominerende sæt (dominerende sæt, der fremkaldte forbundne undergrafer). Et dominerende sæt med én vertex kan også kaldes et universelt toppunkt. Dominationsnummeret på en graf er antallet af hjørner i det mindste dominerende sæt.

E

E
E ( G ) er kanterne af G ; se kantindstilling .
øre
Et øre af en graf er en sti, hvis endepunkter kan falde sammen, men hvor der ellers ikke er gentagelser af hjørner eller kanter.
nedbrydning af øret
En øretnedbrydning er en opdeling af kanterne af en graf i en række ører, som hver af deres endepunkter (efter det første) tilhører et tidligere øre, og hver af dens indre punkter ikke tilhører noget tidligere øre. Et åbent øre er en enkel sti (et øre uden gentagne hjørner), og et åbent øret nedbrydning er en ørededbrydning, hvor hvert øre efter det første er åbent; en graf har et åbent øret nedbrydning, hvis og kun hvis den er forbundet. Et øre er ulige, hvis det har et ulige antal kanter, og et ulige øretnedbrydning er en øretnedbrydning, hvor hvert øre er ulige; en graf har en ulige nedbrydning af øret, hvis og kun hvis den er faktor-kritisk.
excentricitet
Ekscentriciteten af ​​et toppunkt er den fjerneste afstand fra det til ethvert andet toppunkt.
kant
En kant er (sammen med hjørner) en af ​​de to grundlæggende enheder, hvorfra grafer er konstrueret. Hver kant har to (eller i hypergrafer, flere) hjørner, som den er knyttet til, kaldet dens endepunkter. Kanter kan være rettet eller ikke -styret; uorienterede kanter kaldes også linjer og rettede kanter kaldes også buer eller pile. I en uorienteret simpel graf kan en kant repræsenteres som sættet af dens hjørner, og i en rettet simpel graf kan den repræsenteres som et ordnet par af dens hjørner. En kant, der forbinder hjørner x og y, er undertiden skrevet xy .
kantskæring
Et sæt af kant s hvis fjernelse afbryder den graf . Et snit med en kant kaldes en bro , isthmus eller skåret kant .
kant sæt
Sættet med kanter på en given graf G , undertiden betegnet med E ( G ) .
kantløs graf
Den kantløse graf eller den helt afbrudte graf på et givet sæt hjørner er den graf, der ikke har kanter. Det kaldes undertiden den tomme graf, men dette udtryk kan også referere til en graf uden hjørner.
indlejring
En grafindlejring er en topologisk fremstilling af en graf som en delmængde af et topologisk rum med hvert toppunkt repræsenteret som et punkt, hver kant repræsenteret som en kurve med kantens endepunkter som kurvens endepunkter og ingen andre skæringspunkter mellem hjørner eller kanter. En plan graf er en graf, der har en sådan indlejring i det euklidiske plan, og en toroidal graf er en graf, der har en sådan indlejring i en torus. De slægt af en graf er de mindst mulige slægt af en todimensional manifold , på hvilken den kan indlejres.
tom graf
1. En kantløs graf på et ikke -fritaget sæt hjørner.
2. Ordren-nul-grafen , en graf uden hjørner og ingen kanter.
ende
En ende på en uendelig graf er en ækvivalensklasse af stråler, hvor to stråler er ækvivalente, hvis der er en tredje stråle, der indeholder uendeligt mange hjørner fra dem begge.
endepunkt
Et af de to hjørner, der er forbundet med en given kant, eller et af det første eller sidste toppunkt for en gåtur, sti eller sti. Det første endepunkt for en given rettet kant kaldes halen, og det andet endepunkt kaldes hovedet .
optælling
Grafopregning er problemet med at tælle graferne i en given klasse af grafer som en funktion af deres rækkefølge. Mere generelt kan opregningsproblemer enten referere til problemer med at tælle en bestemt klasse af kombinatoriske objekter (såsom klik, uafhængige sæt, farvelægninger eller spændstræer) eller algoritmisk opregning af alle sådanne objekter.
Eulerian
En euleriansk sti er en gåtur, der bruger hver kant af en graf nøjagtigt en gang. Et Eulerian -kredsløb (også kaldet en Eulerian -cyklus eller en Euler -tur) er en lukket gåtur, der bruger hver kant nøjagtigt en gang. En Eulerian -graf er en graf, der har et Eulerian -kredsløb. For en ikke -styret graf betyder det, at grafen er forbundet, og hvert toppunkt har en jævn grad. For en rettet graf betyder det, at grafen er stærkt forbundet, og hvert toppunkt har in-grad svarende til ud-graden. I nogle tilfælde løsnes forbindelseskravet, og en graf, der kun opfylder gradskravene, kaldes Eulerian.
også selvom
Kan deles med to; for eksempel er en lige cyklus en cyklus, hvis længde er lige.
ekspander
En ekspanderingsgraf er en graf, hvis kantudvidelse, toppunktsudvidelse eller spektral ekspansion er afgrænset fra nul.
udvidelse
1. Kanten ekspansion, isoperimetriske nummer, eller Cheeger konstant af en graf G er minimumsforholdet over delmængder S på højst halvdelen af knudepunkter af G , af antallet af kanter forlader S til antallet af knuder i S .
2. Spidsekspansionen, toppunktet isoperimetrisk tal eller forstørrelsen af ​​en graf G er minimumsforholdet, over delmængder S på højst halvdelen af G -hjørnerne , af antallet af hjørner uden for, men støder op til S, til antallet af hjørner i S .
3. Den entydige nabo ekspansion af en graf G er minimumsforholdet over delmængder på højst halvdelen af knudepunkter af G , af antallet af knuder uden S men støder op til en unik toppunkt i S til antallet af knuder i S .
4. Den spektrale ekspansion af en d -regulær graf G er spektralgabet mellem den største egenværdi d i dens adjacensmatrix og den næststørste egenværdi.
5. En familie af grafer har afgrænset ekspansion, hvis alle dens r -flade mindreårige har et forhold mellem kanter og hjørner afgrænset af en funktion af r og polynomudvidelse, hvis funktionen af r er et polynom.

F

ansigt
I en plan graf eller grafindlejring er en tilsluttet komponent i undersættet af planen eller overfladen af ​​indlejringen, der er adskilt fra grafen. For en indlejring i flyet vil alle undtagen ét ansigt være afgrænset; det ene usædvanlige ansigt, der strækker sig til det uendelige, kaldes det ydre ansigt.
faktor
En faktor i en graf er en spændende undergraf: et undergraf, der omfatter alle kurvens hjørner. Udtrykket bruges primært i forbindelse med almindelige subgrafer: en k -faktor er en faktor, der er k -regelmæssig. Især en 1 -faktor er det samme som en perfekt matchning. En faktor -kritisk graf er en graf, for hvilken sletning af et hvert toppunkt producerer en graf med en 1 -faktor.
faktorisering
En graffaktorisering er en opdeling af grafens kanter i faktorer; en k -faktorisering er en opdeling i k -faktorer. For eksempel en 1 -factorization er en kant farvning med den yderligere egenskab, at hver top er indfaldende til en kant af hver farve.
familie
Et synonym for klasse .
begrænset
En graf er endelig, hvis den har et begrænset antal hjørner og et begrænset antal kanter. Mange kilder antager, at alle grafer er begrænsede uden udtrykkeligt at sige det. En graf er lokalt endelig, hvis hvert toppunkt har et begrænset antal indfaldende kanter. En uendelig graf er en graf, der ikke er endelig: den har uendeligt mange hjørner, uendeligt mange kanter eller begge dele.
første ordre
Den første ordens logik i grafer er en form for logik, hvor variabler repræsenterer hjørner af en graf, og der findes et binært prædikat til at teste, om to hjørner er tilstødende. At skelne fra anden ordens logik, hvor variabler også kan repræsentere sæt af hjørner eller kanter.
-klap
For et sæt knudepunkter X , en X -flap er en tilsluttet komponent af det inducerede undergrafen dannet ved at slette X . Klappeterminologien bruges almindeligvis i forbindelse med havne , funktioner, der kortlægger små sæt hjørner til deres klapper. Se også broen til en cyklus, som enten er en klap af cyklushjørnerne eller en akkord af cyklussen.
forbudt
En forbudt grafkarakterisering er en karakterisering af en familie af grafer som værende graferne, der ikke har visse andre grafer som undergrafer, inducerede undergrafer eller mindreårige. Hvis H er en af ​​de grafer, der ikke forekommer som en subgraf, induceret subgraf eller mindre, så siges H at være forbudt.
Skov
En skov er en uorienteret graf uden cykler (en usammenhængende forening af urodede træer) eller en rettet graf dannet som en uforenet forening af rodfæstede træer.
Frucht
1.   Robert Frucht
2. Frucht -grafen , en af ​​de to mindste kubikgrafer uden utrivelige symmetrier.
3.   Frucht's sætning om, at hver begrænset gruppe er gruppen af ​​symmetrier i en endelig graf.
fuld
Synonym for induceret .
funktionel graf
En funktionel graf er en rettet graf, hvor hvert toppunkt har en grad i en grad. Tilsvarende er en funktionel graf en maksimalt rettet pseudoforest.

G

G
En variabel, der ofte bruges til at betegne en graf.
slægt
Slægten i en graf er den mindste slægt af en overflade, hvorpå den kan indlejres; se indlejring .
geodesisk
Som et substantiv er en geodesik et synonym for den korteste vej . Når det bruges som et adjektiv, betyder det relateret til korteste stier eller korteste sti -afstande.
kæmpe stor
I teorien om tilfældige grafer er en kæmpe komponent en forbundet komponent, der indeholder en konstant brøkdel af grafens hjørner. I standardmodeller af tilfældige grafer er der typisk højst en kæmpe komponent.
omkreds
Den omkreds af en graf er længden af sin korteste cyklus.
kurve
Det grundlæggende formål med studiet i grafteori, et system med hjørner, der er parvis forbundet med kanter. Ofte underopdelt i rettede grafer eller uorienterede grafer alt efter, om kanterne har en retning eller ej. Blandede grafer omfatter begge typer kanter.
grådig
Produceret af en grådig algoritme . For eksempel er en grådig farvning af en graf en farve frembragt ved at betragte hjørnerne i en eller anden sekvens og tildele hvert toppunkt den første tilgængelige farve.
Grötzsch
1.   Herbert Grötzsch
2. Grötzsch-grafen , den mindste trekantfrie graf, der kræver fire farver i enhver passende farve.
3.   Grötzschs sætning om, at trekantfrie plane grafer altid kan farves med højst tre farver.
Grundy nummer
1. Grundy-tallet i en graf er det maksimale antal farver, der frembringes af en grådig farve , med en dårligt valgt toppunktsordre.

H

H
En variabel ofte til at betegne en graf, især når en anden graf allerede er blevet betegnet med G .
H -farvning
En H -coloring af en graf G (hvor H er også en graf) er en homomorfi fra H til G .
H -fri
En graf er H -fri, hvis den ikke har en induceret subgraf isomorf for H , det vil sige hvis H er en forbudt induceret subgraf. De H -fri grafer er familien af alle grafer (eller ofte, alle endelige grafer), som er H -fri. For eksempel er de trekantfrie grafer de grafer, der ikke har en trekantgraf som undergraf. Ejendommen ved at være H -fri er altid arvelig. En graf er H -Mindre-gratis, hvis det ikke har en mindre isomorf til H .
Hadwiger
1.   Hugo Hadwiger
2. Hadwiger -nummeret på en graf er størrelsesordenen for den største komplette minor på grafen. Det kaldes også kontraktionskliknummeret eller homomorfismen.
3. Hadwiger -formodningen er formodningen om, at Hadwiger -tallet aldrig er mindre end det kromatiske tal.
Hamiltonian
En hamiltonske sti eller en Hamiltonsk cyklus er en simpel spændingssti eller simpel spændingscyklus: den dækker alle hjørner i grafen nøjagtigt én gang. En graf er Hamiltonian, hvis den indeholder en Hamiltonian -cyklus, og kan spores, hvis den indeholder en Hamiltonian -sti.
tilflugtssted
En k - paradis er en funktion, der kortlægger hvert sæt X af færre end k knudepunkter til en af sine flapper, ofte opfylde yderligere konsistens betingelser. Ordenen for et tilflugtssted er tallet k . Havens kan bruges til at karakterisere træbredden af ​​endelige grafer og enderne og Hadwiger -antallet af uendelige grafer.
højde
1. Højden af en knude i et rodfæstet træ er antallet af kanter i en maksimal bane, der går væk fra roden (dvs. dens noder har en strengt stigende dybde), der starter ved den knude og ender ved et blad.
2. Højden på et rodfæstet træ er højden af ​​dets rod. Det vil sige, at træets højde er antallet af kanter på en længst mulig sti, der går væk fra roden, der starter ved roden og ender ved et blad.
3. Højden på en rettet acyklisk graf er den maksimale længde af en rettet sti i denne graf.
arvelig
En arvelig egenskab af grafer er en egenskab, der er lukket under inducerede subgraphs: hvis G har en arvelig egenskab, så så skal enhver induceret delgraf af G . Sammenlign monoton (lukket under alle undergrafer) eller mindre lukkede (lukkede under mindreårige).
sekskant
En simpel cyklus bestående af præcis seks kanter og seks hjørner.
hul
Et hul er en induceret cyklus med længde fire eller mere. Et ulige hul er et hul med ulige længder. Et anti-hul er en induceret subgraf af orden fire, hvis komplement er en cyklus; tilsvarende er det et hul i komplementgrafen. Denne terminologi bruges hovedsageligt i forbindelse med perfekte grafer, der er kendetegnet ved den stærke perfekte grafsætning som værende graferne uden ulige huller eller ulige antihuller. De hulfrie grafer er de samme som akkordgraferne .
homomorf ækvivalens
To grafer er homomorfe ækvivalente, hvis der findes to homomorfismer, en fra hver graf til den anden graf.
homomorfisme
1. En grafhomomorfisme er en kortlægning fra toppunktsættet i en graf til toppunktsættet i en anden graf, der kortlægger tilstødende hjørner til tilstødende hjørner. Denne type kortlægning mellem grafer er den, der oftest bruges i kategoriteoretiske tilgange til grafteori. En korrekt graffarvning kan tilsvarende beskrives som en homomorfisme til en komplet graf.
2. Graden homomorfisme i et diagram er et synonym for dets Hadwiger -nummer , rækkefølgen af ​​den største clique -minor.
hyperkant
En kant i et hypergraf , der har et vilkårligt antal slutpunkter, i modsætning til kravet om, at grafernes kanter har præcis to slutpunkter.
hyperkube
En hyperkubegraf er en graf dannet ud fra hjørnerne og kanterne på en geometrisk hyperkube .
hypergraf
Et hypergraf er en generalisering af en graf, hvor hver kant (kaldet en hyperkant i denne sammenhæng) kan have mere end to slutpunkter.
hypo-
Dette præfiks, i kombination med en grafegenskab, angiver en graf, der ikke har egenskaben, men sådan at hver subgraf, der dannes ved at slette et enkelt toppunkt, har egenskaben. For eksempel er en hypohamiltonsk graf en, der ikke har en Hamiltonsk cyklus, men for hvilken hver en-toppunkts sletning producerer en Hamiltonian subgraf. Sammenlign kritisk , der bruges til grafer, der har en egenskab, men som hver eneste-toppunkts sletning ikke gør.

jeg

i grad
Antallet af indgående kanter i en rettet graf; se grad .
forekomst
En forekomst i en graf er et vertex-edge-par, således at toppunktet er et endepunkt for kanten.
forekomstmatrix
Den Forekomsten matrix af en graf er en matrix, hvis rækker er indekseret af knudepunkter i grafen, og hvis søjler er indekseret af kanter, med en en i cellen for række i og søjle j når vertex jeg og kant j er hændelsen, og en nul ellers.
utilsigtet hændelse
Forholdet mellem en kant og et af dens endepunkter.
uforlignelighed
En uforlignelighed graf er supplementet til en sammenlignelighed graf ; se sammenlignelighed .
uafhængig
1. Et uafhængigt sæt er et sæt hjørner, der fremkalder et kantløst undergraf. Det kan også kaldes et stabilt sæt eller en coclique. Den uafhængighed nummer α ( G ) er størrelsen af den maksimale uafhængige sæt .
2. I den grafiske matroid af en graf er et undersæt af kanter uafhængigt, hvis den tilsvarende undergraf er et træ eller en skov. I den bicirkulære matroid er en delmængde af kanter uafhængig, hvis den tilsvarende undergraf er en pseudoforest .
ligegyldighed
En ligegyldighedsgraf er et andet navn på en korrekt intervalgraf eller enhedsintervallgraf; se ordentligt .
induceret
En induceret subgraf eller fuld subgraf af en graf er en subgraf, der er dannet ud fra en delmængde af hjørner og fra alle de kanter, der har begge endepunkter i delsættet. Særlige tilfælde omfatter inducerede stier og inducerede cyklusser , inducerede subgrafer, der er stier eller cyklusser.
induktiv
Synonym for degenereret .
uendelig
En uendelig graf er en, der ikke er endelig; se endelig .
indre
Et toppunkt på en sti eller et træ er internt, hvis det ikke er et blad; det vil sige, hvis dens grad er større end en. To veje er internt adskilte (nogle mennesker kalder det uafhængige ), hvis de ikke har nogen toppunkter til fælles, undtagen de første og sidste.
vejkryds
1. Skæringspunktet mellem to grafer er deres største fælles undergraf, grafen dannet af de hjørner og kanter, der tilhører begge grafer.
2. En skæringsgraf er en graf, hvis hjørner svarer til sæt eller geometriske objekter, med en kant mellem to hjørner nøjagtigt, når de tilsvarende to sæt eller objekter har et ikke -fritliggende skæringspunkt. Adskillige klasser af grafer kan defineres som skæringspunkterne grafer af visse typer objekter, for eksempel kordelængder grafer (vejkryds grafer af undertræer af et træ), cirkel grafer (vejkryds grafer af korder af en cirkel), interval grafer (vejkryds grafer af intervaller af en linje), linjediagrammer (skæringsgrafer for kanterne af en graf) og klikgrafer (skæringsgrafer for de maksimale klik i en graf). Hver graf er en skæringsgraf for nogle grupper af sæt, og denne familie kaldes en skæringsrepræsentation af grafen. Det vejkryds Antallet af en graf G er det mindste samlede antal elementer i enhver vejkryds repræsentation af G .
interval
1. En intervalgraf er en skæringsgraf med intervaller på en linje .
2. Intervallet [ u , v ] i en graf er foreningen af ​​alle korteste veje fra u til v .
3. Intervallykkelse er et synonym for sti -bredde .
uændret
Et synonym for ejendom .
omvendt pil
En pil med en modsat retning i forhold til en anden pil. Pilen ( y , x ) er pilens omvendte pil ( x , y ) .
isoleret
Et isoleret toppunkt i en graf er et toppunkt, hvis grad er nul, det vil sige et toppunkt uden indfaldende kanter.
isomorf
To grafer er isomorfe, hvis der er en isomorfisme mellem dem; se isomorfisme .
isomorfisme
En grafisomorfisme er en en-til-en forekomst, der bevarer korrespondance mellem hjørnerne og kanterne på en graf til hjørnerne og kanterne på en anden graf. To grafer relateret på denne måde siges at være isomorfe.
isoperimetrisk
Se udvidelse .
landtange
Synonym for bridge , i betydningen en kant, hvis fjernelse afbryder grafen.

K

K
For notationen for komplette grafer, komplette topartsgrafer og komplette flerpartsgrafer, se komplet .
κ
κ ( G ) (ved hjælp af det græske bogstav kappa) er størrelsesordenen for den maksimale klik i G ; se klik .
kerne
En kerne af en rettet graf er et sæt hjørner, som er både stabilt og absorberende .
knude
En uundgåelig sektion af en rettet graf . Se knude (matematik) og knudeori .

L

L
L ( G ) er linjediagrammet over G ; se linje .
etiket
1. Information forbundet med et toppunkt eller kant af en graf. En mærket graf er en graf, hvis hjørner eller kanter har etiketter. Udtrykkene toppunktsmærket eller kantmærket kan bruges til at angive, hvilke objekter i en graf der har etiketter. Grafmærkning refererer til flere forskellige problemer med at tildele etiketter til grafer, der er underlagt visse begrænsninger. Se også graffarvning , hvor etiketterne tolkes som farver.
2. I forbindelse med grafopregning siges det, at hjørnerne i en graf er mærket, hvis de alle kan skelnes fra hinanden. For eksempel kan dette gøres sandt ved at rette en en-til-en-korrespondance mellem hjørnerne og heltalene fra 1 til grafens rækkefølge. Når hjørner er mærket, tælles grafer, der er isomorfe for hinanden (men med forskellige toppunktsordninger) som separate objekter. I modsætning hertil, når hjørnerne er umærkede, tælles grafer, der er isomorfe for hinanden, ikke separat.
blad
1. Et bladpunkt eller hængende toppunkt (især i et træ) er et toppunkt, hvis grad er  1 . En bladkant eller vedhængskant er kanten, der forbinder et bladpunkt til sin eneste nabo.
2. En blad magt af et træ er en graf hvis knudepunkter er bladene af træet og hvis kanter forbinde blade, hvis afstand i træet er højst en given tærskel.
længde
I en uvægtet graf er længden af ​​en cyklus, sti eller gåtur antallet af kanter, den bruger. I en vægtet graf kan det i stedet være summen af ​​vægten af ​​kanterne, den bruger. Længde bruges til at definere den korteste vej , omkreds (korteste cykellængde) og længste vej mellem to hjørner i en graf.
niveau
1. Dette er dybden af en knude plus 1, selvom nogle definerer det i stedet for at være synonym for dybde . En nodes niveau i et rodfæstet træ er antallet af noder i stien fra roden til knuden. For eksempel har roden niveau 1, og enhver af dens tilstødende noder har niveau 2.
2. Et sæt af alle knuder med samme niveau eller dybde.
linje
Et synonym for en ikke -styret kant. Den linjegraf L ( G ) af en graf G er en kurve med et toppunkt for hver kant af G og en kant for hvert par af kanter, der deler et slutpunkt i G .
sammenkobling
Et synonym for degeneration .
liste
1. En tilstødelsesliste er en computerrepræsentation af grafer til brug i grafalgoritmer.
2.   Listfarvning er en variation af graffarvning, hvor hvert toppunkt har en liste over tilgængelige farver.
lokal
En lokal egenskab af en graf er en egenskab, der kun bestemmes af kvartererne i hjørnerne i grafen. For eksempel er en graf lokalt endelig, hvis alle dens kvarterer er begrænsede.
sløjfe
En sløjfe eller selvløkke er en kant, hvis endepunkter er det samme toppunkt. Det danner en cyklus med længde 1 . Disse er ikke tilladt i simple grafer.

M

forstørrelse
Synonym for vertex ekspansion .
matchende
En matchning er et sæt kanter, hvor ingen deler noget toppunkt. Et toppunkt matches eller mættes, hvis det er et af endepunkterne for en kant i matchningen. En perfekt matchning eller komplet matchning er en matchning, der matcher hvert toppunkt; det kan også kaldes en 1-faktor og kan kun eksistere, når rækkefølgen er jævn. En næsten perfekt matchning i en graf med ulige rækkefølge er en, der mætter alle undtagen et toppunkt. En maksimal matchning er en matchning, der bruger så mange kanter som muligt; det matchende tal α ′ ( G ) for en graf G er antallet af kanter i en maksimal matchning. En maksimal matchning er en matchning, hvortil der ikke kan tilføjes yderligere kanter.
maksimal
1. Et undergraf af den givne graf G er maksimalt for en bestemt egenskab, hvis den har den egenskab, men ingen anden supergraf af den, der også er en undergraf af G , har også den samme egenskab. Det vil sige, at det er et maksimalt element i undergraferne med ejendommen. For eksempel er en maksimal klik en komplet subgraf, der ikke kan udvides til en større komplet subgraf. Ordet "maksimal" bør skelnes fra "maksimum": en maksimal subgraf er altid maksimal, men ikke nødvendigvis omvendt.
2. En simpel graf med en given egenskab er maksimal for den egenskab, hvis det ikke er muligt at tilføje flere kanter til den (holde toppunktet uændret), samtidig med at både grafens enkelhed og egenskaben bevares. Således er for eksempel en maksimal plan graf en plan graf, således at tilføjelse af flere kanter til den ville skabe en ikke-plan graf.
maksimum
Et undergraf af en given graf G er maksimum for en bestemt egenskab, hvis den er den største undergraf (efter rækkefølge eller størrelse) blandt alle undergrafer med den egenskab. For eksempel er en maksimal klik en af ​​de største klik i en given graf.
median
1. En median af en tredobbelt hjørner, et toppunkt, der tilhører de korteste stier mellem alle par af hjørner, især i mediangrafer og modulgrafer .
2. En median graf er en graf, hvor hver tre hjørner har en unik median.
Meyniel
1. Henri Meyniel, fransk grafteoretiker.
2. En Meyniel -graf er en graf, hvor hver ulige cyklus med længde fem eller flere har mindst to akkorder.
minimal
Et undergraf af en given graf er minimalt for en bestemt egenskab, hvis den har den egenskab, men ingen ordentlig undergravning af den har også den samme egenskab. Det vil sige, at det er et minimalt element i undergraferne med ejendommen.
mindste snit
Et snit, hvis udskæringssæt har minimum totalvægt, muligvis begrænset til udskæringer, der adskiller et udpeget par hjørner; de er kendetegnet ved max-flow min-cut sætning .
mindre
En graf H er en mindre af en anden graf G hvis H , kan opnås ved at slette kanter eller hjørner fra G og kontraherende kanter i G . Det er en lav minor, hvis den kan dannes som en minor på en sådan måde, at subgraferne af G, der blev kontraheret til at danne hjørner af H, alle har en lille diameter. H er en topologisk mindre af G hvis G har en undergraf der er en underafdeling af H . En graf er H -mindre -fri, hvis den ikke har H som minor. En familie af grafer lukkes mindre, hvis den lukkes under mindreårige; den Robertson-Seymour teorem karakteriserer mindre lukkede familier som har et endeligt sæt af forbudte mindreårige.
blandet
En blandet graf er en graf, der kan indeholde både rettede og uorienterede kanter.
modulopbygget
1.   Modulær graf , en graf, hvor hver triple af hjørner har mindst et median toppunkt, der tilhører de korteste stier mellem alle triplepar.
2.   Modulær dekomponering , en nedbrydning af en graf til undergrafer, inden for hvilke alle hjørner forbindes til resten af ​​grafen på samme måde.
3.   Modularitet af en grafklynge, forskellen mellem antallet af kryds-klynge-kanter fra dens forventede værdi.
monoton
En monoton ejendom af grafer er en egenskab, der er lukket under subgraphs: hvis G har en arvelig egenskab, så så skal hver delgraf af G . Sammenlign arvelig (lukket under inducerede subgrafer) eller mindre lukkede (lukkede under mindreårige).
Moore graf
En Moore -graf er en almindelig graf, for hvilken Moore -grænsen er nøjagtigt opfyldt. Moore -grænsen er en ulighed vedrørende graden, diameteren og rækkefølgen af ​​en graf, bevist af Edward F. Moore . Hver Moore -graf er et bur.
multigraf
En multigraf er en graf, der tillader flere adjakenser (og ofte selvsløjfer); en graf, der ikke skal være enkel.
flere tilstødende
En multipel adjacency eller multiple edge er et sæt med mere end en kant, der alle har de samme endepunkter (i samme retning, i tilfælde af rettede grafer). En graf med flere kanter kaldes ofte en multigraf.
mangfoldighed
Mangfoldigheden af ​​en kant er antallet af kanter i en multipel adjacency. Multipliciteten af ​​en graf er den maksimale multiplicitet af en af ​​dens kanter.

N

N
1. For notationen for åbne og lukkede kvarterer, se kvarter .
2. En n bruges ofte (især inden for datalogi) til at angive antallet af hjørner i en given graf.
nabo
nabo
Et toppunkt, der støder op til et givet toppunkt.
kvarter
kvarter
Det åbne kvarter (eller kvarter) for et toppunkt v er subgrafen induceret af alle hjørner, der støder op til v . Det lukkede kvarter er defineret på samme måde, men inkluderer også v selv. Det åbne kvarter v i G kan betegnes N G ( v ) eller N ( v ) , og det lukkede kvarter kan betegnes N G [ v ] eller N [ v ] . Når åbenheden eller lukketheden i et kvarter ikke er specificeret, antages det at være åbent.
netværk
En graf, hvor attributter (f.eks. Navne) er knyttet til noder og/eller kanter.
knudepunkt
Et synonym for toppunkt .
ikke kant
En ikke-kant eller anti-kant er et par hjørner, der ikke er tilstødende; kanterne på komplementgrafen.
null -graf
Se tom graf .

O

ulige
1. En ulige cyklus er en cyklus, hvis længde er ulige. Den ulige omkreds af en ikke-topartet graf er længden af ​​dens korteste ulige cyklus. Et ulige hul er et specielt tilfælde af en ulige cyklus: et der er induceret og har fire eller flere hjørner.
2. Et ulige toppunkt er et toppunkt, hvis grad er ulige. Ved det håndrystende lemma har hver begrænset, uorienteret graf et lige antal ulige hjørner.
3. Et ulige øre er en simpel sti eller simpel cyklus med et ulige antal kanter, der bruges ved ulige øret nedbrydninger af faktor-kritiske grafer; se øre .
4. En ulige akkord er en kant, der forbinder to hjørner, der er en ulige afstand fra hinanden i en lige cyklus. Ulige akkorder bruges til at definere stærkt akkordgrafer .
5. En ulige graf er et specielt tilfælde af en Kneser -graf , der har et toppunkt for hvert ( n -1) -elementundermængde af et (2 n -1) -elementsæt og en kant, der forbinder to undersæt, når deres tilsvarende sæt er usammenhængende.
åben
1. Se kvarter .
2. Se gåtur .
bestille
1. Rækkefølgen af ​​en graf G er antallet af dens hjørner, | V ( G ) | . Variablen n bruges ofte til denne mængde. Se også størrelse , antallet af kanter.
2. En form for logik i grafer ; se første ordre og anden ordre .
3. En rækkefølge eller rækkefølge af en graf er et arrangement af dets hjørner i en sekvens, især i forbindelse med topologisk orden (en rækkefølge af en rettet acyklisk graf, hvor hver kant går fra et tidligere toppunkt til et senere toppunkt i rækkefølgen ) og degenerationsordre (en rækkefølge, hvor hvert toppunkt har minimumsgrad i den inducerede undergravning af det og alle senere hjørner).
4. For rækkefølgen af ​​et tilflugtssted eller bramble, se tilflugtssted og bramble .
orientering
orienteret
1. En orientering af en ikke -styret graf er en tildeling af retninger til dens kanter, hvilket gør den til en rettet graf. En orienteret graf er en, der har fået tildelt en orientering. Så for eksempel er et polytree et orienteret træ; det adskiller sig fra et rettet træ (en arborescens) ved, at der ikke er krav om konsistens i kanterets retninger. Andre særlige former for orientering omfatter turneringer , orienteringer af komplette grafer; stærke orienteringer , orienteringer, der er stærkt forbundet; acykliske orienteringer , orienteringer, der er acykliske; Eulerian orienteringer , orienteringer, der er Eulerian; og transitive orienteringer , orienteringer, der er transitivt lukkede.
2. Orienteret graf, brugt af nogle forfattere som et synonym for en rettet graf .
ud-grad
Se grad .
ydre
Se ansigt .
ydre plan
En ydre plan graf er en graf, der kan indlejres i planet (uden krydsninger), så alle hjørner er på grafens ydre flade.

P

sti
En sti kan enten være en gåtur eller en gåtur uden gentagne hjørner og følgelig kanter (også kaldet en simpel sti), afhængigt af kilden. Vigtige særlige tilfælde omfatter inducerede stier og korteste stier .
nedbrydning af stien
En stiens dekomponering af en graf G er en trænedbrydning, hvis underliggende træ er en sti. Dens bredde er defineret på samme måde som for trænedbrydninger, som en mindre end størrelsen på den største pose. Den mindste bredde af en kurve nedbrydning af G er pathwidth af G .
vejbredde
Den pathwidth af en graf G er den mindste bredde af en vej nedbrydning af G . Det kan også defineres udtrykt ved klike antal et interval færdiggørelse af G . Det er altid mellem båndbredden og G -bredden . Det er også kendt som intervaltykkelse, toppunkts adskillelsesnummer eller nodesøgningsnummer.
vedhæng
Se blad .
Perfekt
1. En perfekt graf er en graf, hvor det kromatiske tal i hvert induceret undergraf svarer til kliknummeret. Den perfekte grafteorem og stærke perfekte grafteorem er to sætninger om perfekte grafer, førstnævnte beviser, at deres komplementer også er perfekte, og sidstnævnte viser, at de er nøjagtigt graferne uden ulige huller eller anti-huller.
2. En graf, der kan bestilles fuldstændigt, er en graf, hvis hjørner kan ordnes på en sådan måde, at en grådig farvelgoritme med denne ordning optimerer farver hver induceret undergraf. De perfekt bestilbare grafer er en underklasse af de perfekte grafer.
3. En perfekt matchning er en matchning, der mætter hvert toppunkt; se matchning .
4. En perfekt 1-faktorisering er en opdeling af kanterne på en graf i perfekte matchninger, så hver to matchning danner en Hamiltonsk cyklus.
perifer
1. En perifer cyklus eller ikke-separerende cyklus er en cyklus med højst en bro.
2. En perifer toppunkt er en toppunkt, hvis excentricitet er maksimal. I et træ skal dette være et blad.
Petersen
1.   Julius Petersen (1839–1910), dansk grafteoretiker.
2. Petersen-grafen , en 10-toppunkts 15-kantet graf, der ofte bruges som et modeksempel.
3.   Petersens sætning om, at hver brofri kubikgraf har en perfekt matchning.
plan
En plan graf er en graf, der har en indlejring i det euklidiske plan. En plan graf er en plan graf, for hvilken en bestemt indlejring allerede er blevet rettet. En k -plan graf er en, der kan tegnes i flyet med højst k krydsninger pr. Kant.
polytree
Et polytree er et orienteret træ; ækvivalent, en rettet acyklisk graf, hvis underliggende ikke -styrede graf er et træ.
strøm
1. En grafeffekt G k af en graf G er en anden graf på det samme toppunktssæt; to knudepunkter er hosliggende i G k , når de er i afstand på højst k i G . En bladkraft er et nært beslægtet begreb, der stammer fra et træs kraft ved at tage undergrafen induceret af træets blade.
2.   Power graf analyse er en metode til at analysere komplekse netværk ved at identificere kliker, bicliques og stjerner i netværket.
3.   Magtlove i gradfordelingerne af skalafrie netværk er et fænomen, hvor antallet af hjørner af en given grad er proportional med graden af ​​graden.
forgænger
Et toppunkt, der kommer før et givet toppunkt i en rettet sti .
passende
1. En ordentlig undergraf er en undergraf, der fjerner mindst et toppunkt eller en kant i forhold til hele grafen; for endelige grafer er rigtige subgrafer aldrig isomorfe for hele grafen, men for uendelige grafer kan de være.
2. En korrekt farvning er en tildeling af farver til hjørnerne på en graf (en farve), der tildeler forskellige farver slutpunkterne for hver kant; se farve .
3. En korrekt intervalgraf eller korrekt cirkelbue -graf er en skæringsgraf for en samling af henholdsvis intervaller eller cirkelbuer, således at intet interval eller en bue indeholder et andet interval eller en anden bue. Korrekte intervalgrafer kaldes også enhedsintervallgrafer (fordi de altid kan repræsenteres ved enhedsintervaller) eller ligegyldighedsgrafer.
ejendom
En grafegenskab er noget, der kan være sandt for nogle grafer og falsk for andre, og det afhænger kun af grafstrukturen og ikke af tilfældige oplysninger såsom etiketter. Grafegenskaber kan tilsvarende beskrives i form af klasser af grafer (graferne, der har en given egenskab). Mere generelt kan en grafegenskab også være en funktion af grafer, der igen er uafhængig af tilfældig information, såsom størrelsen, rækkefølgen eller graden af ​​sekvens af en graf; denne mere generelle definition af en ejendom kaldes også en invariant af grafen.
pseudoforest
En pseudoforest er en uorienteret graf, hvor hver tilsluttet komponent højst har en cyklus, eller en rettet graf, hvor hvert toppunkt højst har en udgående kant.
pseudograf
En pseudograf er en graf eller multigraf, der tillader selvsløjfer.

Q

kvasi-linjediagram
En kvasi-linjediagram eller en lokalt co-topartet graf er en graf, hvor det åbne kvarter for hvert toppunkt kan opdeles i to klik. Disse grafer er altid klofrie, og de inkluderer som et specielt tilfælde linjediagrammerne . De bruges i strukturteorien for klofrie grafer.
koger
En dirren er en rettet multigraf, som den bruges i kategoriteori . Kanterne på en dirren kaldes pile.

R

radius
Radius af en graf er minimums -excentriciteten for ethvert toppunkt.
Ramanujan
En Ramanujan -graf er en graf, hvis spektrale ekspansion er så stor som muligt. Det vil sige, at det er en d -regulær graf, sådan at den næststørste egenværdi af dens adjacensmatrix højst er .
stråle
En stråle i en uendelig graf er en uendelig enkel sti med præcis ét endepunkt. De ender af en graf er ækvivalensklasser af stråler.
tilgængelighed
Evnen til at komme fra et toppunkt til et andet inden for en graf .
nås
Har en bekræftelig tilgængelighed . Et toppunkt y siges at være tilgængeligt fra et toppunkt x, hvis der findes en vej fra x til y .
genkendelig
I forbindelse med rekonstruktionstanken er en grafegenskab genkendelig, hvis dens sandhed kan bestemmes ud fra grafens dæk. Mange grafegenskaber er kendt for at være genkendelige. Hvis rekonstruktionstanken er sand, kan alle grafegenskaber genkendes.
rekonstruktion
Den genopbygning formodninger , at hver ikke-orienteret graf G er entydigt bestemt af dets dæk , en multisættet grafer dannet ved at fjerne en vinkelspids fra G på alle mulige måder. I denne sammenhæng er rekonstruktion dannelsen af ​​en graf fra dens dæk.
rektangel
En simpel cyklus bestående af præcis fire kanter og fire hjørner.
fast
En graf er d -regelmæssig, når alle dens hjørner har grad d . En almindelig graf er en graf, der er d -regelmæssig for nogle d .
almindelig turnering
En almindelig turnering er en turnering, hvor in-grad er lig med out-grad for alle hjørner.
baglæns
Se transponering .
rod
1. Et angivet toppunkt i en graf, især i rettede træer og rodfæstede grafer .
2. Den omvendte handling til en grafeffekt : en k th rod af en graf G er en anden graf på det samme toppunktssæt, således at to hjørner er tilstødende i G, hvis og kun hvis de har afstand højst k i roden.

S

anden ordre
Den anden ordens logik af grafer er en form for logik, hvor variabler kan repræsentere hjørner, kanter, sæt af hjørner og (nogle gange) sæt kanter. Denne logik indeholder prædikater for at teste, om et toppunkt og en kant er hændende, samt om et toppunkt eller en kant tilhører et sæt. At skelne fra første ordens logik, hvor variabler kun kan repræsentere hjørner.
mættet
Se matchning .
søgenummer
Nodesøgningsnummer er et synonym for stibredde .
selvsløjfe
Synonym for loop .
adskiller toppunkt
Se artikulationspunkt .
adskillelsesnummer
Vertex -adskillelsesnummer er et synonym for vejbredde .
enkel
1. En simpel graf er en graf uden sløjfer og uden flere adjakenser. Det vil sige, at hver kant forbinder to forskellige endepunkter, og ingen to kanter har de samme endepunkter. En simpel kant er en kant, der ikke er en del af en multipel adjacency. I mange tilfælde antages grafer at være enkle, medmindre andet er angivet.
2. En simpel sti eller en simpel cyklus er en sti eller cyklus, der ikke har gentagne hjørner og følgelig ingen gentagne kanter.
håndvask
En vask i en rettet graf er et toppunkt uden udgående kanter (ud-grad er lig med 0).
størrelse
Størrelsen på en graf G er antallet af kanterne, | E ( G ) | . Variablen m bruges ofte til denne mængde. Se også rækkefølge , antallet af hjørner.
lille verdens netværk
Et lille verden netværk er en graf, hvor de fleste noder ikke er naboer til hinanden, men de fleste noder kan nås fra hver anden knude med et lille antal hop eller trin. Specifikt er et lille verden netværk defineret til at være en graf, hvor den typiske afstand L mellem to tilfældigt valgte noder (antallet af nødvendige trin) vokser proportionalt med logaritmen for antallet af noder N i netværket
snark
En snark er en enkel, forbundet, broløs kubikgraf med kromatisk indeks lig med 4.
kilde
En kilde i en rettet graf er et toppunkt uden indgående kanter (grad er lig med 0).
plads
I algebraisk grafteori kan flere vektorrum over det binære felt være forbundet med en graf. Hver har sæt kanter eller hjørner for sine vektorer og symmetrisk forskel af sæt som sin vektorsumoperation. Den kant rum er rummet af alle sæt kanter, og Isse rum er rummet af alle sæt knuder. Den afskårne rum er et underrum af kanten plads, der har de afskårne-sæt af grafen som dens elementer. Den cyklus rum har de Eulerian udspændende subgraphs som dens elementer.
skruenøgle
En skruenøgle er en (normalt sparsom) graf, hvis korteste sti -afstande er omtrentlige dem i en tæt graf eller et andet metrisk rum. Variationer omfatter geometriske skruenøgler , grafer, hvis hjørner er punkter i et geometrisk rum; træsnøgler , der spænder over træer i en graf, hvis afstande er omtrentlige til grafens afstande, og grafnøgler, sparsomme undergrafer af en tæt graf, hvis afstande tilnærmer sig den originale grafs afstande. En grådig skruenøgle er en grafnøgle konstrueret af en grådig algoritme, generelt en, der betragter alle kanter fra korteste til længste og beholder dem, der er nødvendige for at bevare afstanden tilnærmelse.
spændende
En undergraf spænder over, når den omfatter alle hjørnerne i den givne graf. Vigtige sager omfatter spænding af træer , spændende undergrafer, der er træer, og perfekte matchninger , der spænder over undergrafer, der er matchninger. En spændende subgraf kan også kaldes en faktor , især (men ikke kun), når den er regelmæssig.
sparsom
En sparsom graf er en, der har få kanter i forhold til antallet af hjørner. I nogle definitioner burde den samme egenskab også være sand for alle undergrafer af den givne graf.
spektral
spektrum
Spektret for en graf er samlingen af egenværdier af dets adjacensmatrix. Spektral grafteori er den gren af ​​grafteori, der bruger spektre til at analysere grafer. Se også spektral ekspansion .
dele
1. En delt graf er en graf, hvis hjørner kan opdeles i en klik og et uafhængigt sæt. En beslægtet klasse af grafer, de dobbeltsplittede grafer, bruges i beviset på den stærke perfekte grafsætning.
2. En opdeling af en vilkårlig graf er en opdeling af dens hjørner i to ikke -undgåede undergrupper, således at kanterne, der spænder over dette snit, danner et komplet todelt subgraf. Splittene i en graf kan repræsenteres af en træstruktur kaldet dens opdelte nedbrydning . En split kaldes en stærk split, når den ikke krydses af nogen anden split. En splittelse kaldes nontrivial, når begge sider har mere end et toppunkt. En graf kaldes prime, når den ikke har ikke -private opdelinger.
firkant
1. Kvadratet på en graf G er graf magt G 2 ; i den anden retning er G kvadratroden af G 2 . Den halve kvadrat af en todelt graf er subgrafen af ​​dens firkant induceret af den ene side af todelen.
2. En firkant er en plan graf, der kan tegnes, så alle afgrænsede flader er 4-cyklusser og alle hjørner af grad ≤ 3 tilhører den ydre flade.
3. En firkantet gittergraf er en gittergraf, der er defineret ud fra punkter i flyet med heltalskoordinater forbundet med enhedslængdekanter.
stabil
Et stabilt sæt er et synonym for et uafhængigt sæt .
stjerne
En stjerne er et træ med et indre toppunkt; tilsvarende er det en komplet todelt graf K 1, n for nogle n ≥ 2 . Det særlige tilfælde af en stjerne med tre blade kaldes en klo.
styrke
Den styrken af en graf er forholdet mellem antallet af kanter er fjernet fra grafen til komponenter skabt minimum, over alle mulige flytning; det er analogt til sejhed, baseret på fjernelse af toppunkt.
stærk
1. For stærk forbindelse og stærkt forbundne komponenter i rettet grafer, se tilsluttet og komponent . En stærk orientering er en orientering, der er stærkt forbundet; se orientering .
2. For den stærke perfekte graf sætning , se perfekt .
3. En stærkt regelmæssig graf er en regelmæssig graf, hvor hver to tilstødende hjørner har samme antal delte naboer, og hver to ikke-tilstødende hjørner har samme antal delte naboer.
4. En stærkt akkordgraf er en akkordgraf, hvor hver lige cyklus med længde seks eller flere har en ulige akkord.
5. En stærkt perfekt graf er en graf, hvor hver induceret subgraf har et uafhængigt sæt, der opfylder alle maksimale klik. De Meyniel grafer kaldes også "meget stærkt perfekt grafer", fordi i dem, hver vertex tilhører en sådan uafhængig sæt.
underskov
Et undergraf af en skov .
undergraf
En delgraf af en graf G er en anden graf dannet ud fra en delmængde af knuder og kanter af G . Spidsundersættet skal omfatte alle endepunkter for kantundersættet, men kan også omfatte yderligere hjørner. En spændende subgraf er en, der omfatter alle hjørner af grafen; en induceret subgraf er en, der omfatter alle de kanter, hvis endepunkter tilhører toppunktsundermængden.
undertræ
Et undertræ er et forbundet undergraf af et træ. Nogle gange, for rodfæstede træer, er undertræer defineret til at være en særlig type forbundet subgraf, dannet af alle hjørner og kanter, der kan nås fra et valgt toppunkt.
efterfølger
Et toppunkt, der kommer efter et givet toppunkt i en rettet sti .
superkoncentrator
En superkoncentrator er en graf med to udpegede og lige store undersæt af hjørner I og O , således at der for hver to lige store undersæt S af I og T O eksisterer en familie af uensartede stier, der forbinder hvert toppunkt i S med et toppunkt i T . Nogle kilder kræver desuden, at en superkoncentrator er en rettet acyklisk graf, med I som dens kilder og O som sine synke.
supergraf
En graf dannet ved at tilføje hjørner, kanter eller begge dele til en given graf. Hvis H er en delgraf af G , derefter G er en supergraph af H .

T

theta
1. En theta -graf er foreningen af ​​tre internt adskilte (enkle) stier, der har de samme to adskilte endepunkter.
2. Theta -grafen for en samling af punkter i det euklidiske plan er konstrueret ved at konstruere et system af kegler, der omgiver hvert punkt og tilføjer en kant pr. Kegle, til det punkt, hvis projektion på en central stråle af keglen er mindst.
3. Lovász -tallet eller Lovász theta -funktionen i en graf er en graf invariant relateret til kliknummeret og kromatisk tal, der kan beregnes i polynomtid ved hjælp af semidefinit programmering.
topologisk
1. En topologisk graf er en repræsentation af kurvens hjørner og kanter ved punkter og kurver i planet (ikke nødvendigvis at undgå krydsninger).
2.   Topologisk grafteori er studiet af grafindlejringer.
3.   Topologisk sortering er det algoritmiske problem med at arrangere en rettet acyklisk graf i en topologisk rækkefølge, en toppunktsekvens, så hver kant går fra et tidligere toppunkt til et senere toppunkt i sekvensen.
helt afbrudt
Synonym for kantløs .
tur
En lukket sti, en gåtur, der starter og slutter ved det samme toppunkt og ikke har gentagne kanter. Euler -ture er ture, der bruger alle grafens kanter; se Eulerian .
turnering
En turnering er en orientering af en komplet graf; det vil sige, det er en rettet graf, så hver to hjørner er forbundet med nøjagtigt en rettet kant (går kun i en af ​​de to retninger mellem de to hjørner).
sporbar
En sporbar graf er en graf, der indeholder en Hamiltonsk sti.
sti
En tur uden gentagne kanter.
transitive
At have at gøre med den transitive ejendom . Den transitive lukning af en given rettet graf er en graf på det samme toppunktssæt, der har en kant fra et toppunkt til et andet, når den originale graf har en sti, der forbinder de samme to hjørner. En transitiv reduktion af en graf er en minimal graf med den samme transitive lukning; styrede acykliske grafer har en unik transitiv reduktion. En transitiv orientering er en orientering af en graf, der er dens egen transitive lukning; den findes kun for sammenlignelighedsgrafer .
gennemføre
Den transponerede graf af en given rettet kurve er en kurve på de samme knudepunkter, med hver kant vendt i retning. Det kan også kaldes grafens omvendte eller omvendte.
træ
1. Et træ er en uorienteret graf, der både er forbundet og acyklisk, eller en rettet graf, hvor der findes en unik gang fra et toppunkt (træets rod) til alle resterende hjørner.
2. Et k -træ er en graf, der dannes ved at lime ( k + 1) -cliques sammen på delte k -cliques. Et træ i almindelig forstand er et 1 -træ ifølge denne definition.
nedbrydning af træ
En trænedbrydning af en graf G er et træ, hvis noder er mærket med sæt af hjørner af G ; disse sæt kaldes poser. For hvert toppunkt v skal poserne, der indeholder v , fremkalde et træ af træet, og for hver kant uv skal der findes en pose, der indeholder både u og v . Bredden af ​​en trænedbrydning er en mindre end det maksimale antal hjørner i nogen af ​​dens poser; den treewidth af G er den mindste bredde af noget træ nedbrydning af G .
træbredde
Den treewidth af en graf G er den mindste bredde af et træ nedbrydning af G . Det kan også defineres udtrykt ved klike antallet af en akkordiske færdiggørelse af G , i størrelsesordenen en tilflugtssted af G , eller rækkefølgen af en tornebusken af G .
trekant
En cyklus med længde tre i en graf. En trekantfri graf er en uorienteret graf, der ikke har nogen trekantundergrafer.
Turán
1.   Pál Turán
2. En Turán -graf er en afbalanceret komplet flerpartsgraf.
3.   Turáns sætning siger, at Turán-grafer har det maksimale antal kanter blandt alle klikfrie grafer i en given rækkefølge.
4.   Turans murstenfabriksproblem beder om det mindste antal krydsninger i en tegning af en komplet todelt graf.

U

ustyret
En uorienteret graf er en graf, hvor de to slutpunkter for hver kant ikke skelnes fra hinanden. Se også instrueret og blandet . I en blandet graf er en uorienteret kant igen en kant, hvor endepunkterne ikke skelnes fra hinanden.
uniform
En hypergraph er k Ensartede når alle dens kanter har k endpoints og ensartet, når det er k Ensartede for nogle k . For eksempel er almindelige grafer det samme som 2 -ensartede hypergrafer.
universel
1. En universel graf er en graf, der som undergrafer indeholder alle grafer i en given familie af grafer eller alle grafer af en given størrelse eller rækkefølge inden for en given familie af grafer.
2. Et universelt toppunkt (også kaldet en spids eller dominerende toppunkt) er et toppunkt, der støder op til hvert andet toppunkt i grafen. For eksempel har hjulgrafer og tilsluttede tærskelgrafer altid et universelt toppunkt.
3. I grafikkens logik kan et toppunkt, der er universelt kvantificeret i en formel, kaldes et universelt toppunkt for denne formel.
uvægtet graf
En graf, hvis hjørner og kanter s ikke er blevet tildelt vægt s ; det modsatte af en vægtet graf .

V

V
Se toppunktssæt .
valens
Synonym for grad .
toppunkt
Et toppunkt (flertallige hjørner) er (sammen med kanter) en af ​​de to grundlæggende enheder, hvorfra grafer er konstrueret. Hjørner af grafer anses ofte for at være atomobjekter, uden nogen intern struktur.
toppunktskæring
skillesæt
Et sæt af knudepunkter , hvis fjernelse afbryder den graf . Et et-vertex-snit kaldes et artikulationspunkt eller cut-vertex .
toppunkt sæt
Sættet med hjørner af en given graf G , undertiden betegnet med V ( G ) .
hjørner
Se toppunkt .
Vizing
1.   Vadim G. Vizing
2.   Vizing's sætning om, at det kromatiske indeks højst er en mere end maksimalgraden.
3.   Vizing's formodning om dominerende antallet af kartesiske produkter af grafer.
bind
Summen af ​​grader af et sæt hjørner.

W

W
Bogstavet W bruges i notation til hjulgrafer og vindmøllediagrammer . Notationen er ikke standardiseret.
Wagner
1.   Klaus Wagner
2. Wagner-grafen , en Möbius-stige med otte vertex.
3.   Wagners sætning, der karakteriserer plane grafer efter deres forbudte mindreårige.
4. Wagners sætning, der kendetegner K 5 -minorfrie grafer.
En gåtur er en endelig eller uendelig sekvens af kanter, der slutter sig til en sekvens af hjørner . Gåture kaldes også undertiden kæder . En gåtur er åben, hvis dens første og sidste hjørner er tydelige og lukkede, hvis de gentages.
svagt forbundet
En dirigeret graf kaldes svagt forbundet, hvis udskiftning af alle dens kantede kanter med ikke -styrede kanter frembringer en tilsluttet (ikke -styret) graf.
vægt
En numerisk værdi, der er tildelt som en etiket til et toppunkt eller kant på en graf. Vægten af ​​en undergraf er summen af ​​vægten af ​​hjørnerne eller kanterne i den pågældende undergraf.
vægtet graf
En graf, hvis hjørner eller kanter er blevet tildelt vægt s ; mere specifikt har en toppunkt-vægtet graf vægte på sine hjørner og en kantvægtet graf har vægte på sine kanter.
velfarvet
En velfarvet graf er en graf, hvis grådige farvninger bruger samme antal farver.
godt dækket
En godt dækket graf er en graf, hvis maksimale uafhængige sæt har samme størrelse.
hjul
En hjulgraf er en graf dannet ved at tilføje et universelt toppunkt til en simpel cyklus.
bredde
1. Et synonym for degeneration .
2. For andre grafinvarianter kendt som bredde, se båndbredde , grenbredde , klikbredde , stibredde og træbredde .
3. Bredden af ​​en trænedbrydning eller sti -nedbrydning er en mindre end den maksimale størrelse på en af ​​dens poser og kan bruges til at definere træbredde og sti -bredde.
4. Bredden af ​​en rettet acyklisk graf er den maksimale kardinalitet af et antikæde.
vindmølle
En vindmøllediagram er foreningen af ​​en samling klikker, alle i samme rækkefølge som hinanden, med et fælles toppunkt, der tilhører alle klikerne og alle andre hjørner og kanter adskilte.

Se også

Referencer