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.
- gå
- 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å
- Liste over grafteori emner
- Galleri med navngivne grafer
- Grafalgoritmer
- Ordliste over områder inden for matematik