Ordliste over grafteori

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 17. august 2022; checks kræver 2 redigeringer .

Her er samlet definitioner af begreber fra grafteori . Henvisninger til termer i denne ordbog (på denne side) er i kursiv .

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

En

Automorfi - En isomorfi af en graf med sig selv.
En acyklisk graf er en graf uden cyklusser .

B

En grafbase er en minimal delmængde af det sæt af grafhjørner, hvorfra ethvert grafhjørne kan nås.
En uendelig graf er en graf, der har uendeligt mange hjørner og/eller kanter.
Bigraf - se todelt graf .
En blok er en graf uden hængsler .
Blokdesign med parametre (v, k, λ) er en afdækning med multiplicitet λ af en komplet graf på v toppunkter med komplette grafer på k toppunkter.

I

Vertex valens - se vertex grad .
Vertex , node - grundlæggende koncept : et punkt, hvor kanter og/eller buer kan konvergere/udgå. Sættet af hjørner af en graf G er angivet med V(G).
Et toppunktsdæksel er et sæt toppunkter i en graf, således at hver kant falder ind på mindst ét toppunkt fra dette sæt.
Vægten af en kant er den værdi , der er tildelt en given kant på en vægtet graf . Normalt er vægten et reelt tal , i hvilket tilfælde det kan fortolkes som " længden " af kanten.
En vægtet graf er en graf , hvis hver kant er tildelt en bestemt værdi ( kantvægt ). Se mærket graf .
Et hængende toppunkt er et toppunkt , hvis grad er lig med 1 (det vil sige ). $d(v)=1$

En fuldstændig afbrudt graf er en almindelig graf på grad 0, det vil sige en graf uden kanter .
Højden af et træ er den længste vej fra roden til bladet .

G

En Hamiltonsk graf er en graf, der har en Hamiltonsk cyklus .
En Hamiltonsk sti er en simpel sti i en graf, der indeholder alle hjørnerne af grafen nøjagtigt én gang.
En Hamilton-cyklus er en simpel cyklus i en graf, der indeholder alle toppunkterne i grafen nøjagtigt én gang.
En geometrisk realisering er en figur, hvis spidser svarer til spidserne på grafen, kanter - kanterne på grafen og kanterne i figuren forbinder de spidser, der svarer til spidserne i grafen.
En geometrisk graf er en flad figur af knudepunkter - punkter i planet og kanter - linjer, der forbinder nogle par af knudepunkter. Kan repræsentere enhver graf på mange måder.
En hypergraf er en samling af et sæt toppunkter og et sæt hyperkanter (en delmængde af den n. euklidiske potens af sættet af toppunkter, det vil sige hyperkanter forbinder et vilkårligt antal toppunkter).
Homeomorfe grafer er grafer opnået fra en enkelt graf ved hjælp af en sekvens af kantunderinddelinger.
En flade er et område afgrænset af kanter i en plan graf og indeholder ikke grafens hjørner og kanter. Den ydre del af flyet danner også et ansigt.
Graf er et grundlæggende koncept. Inkluderer et toppunktssæt og et kantsæt , der er en delmængde af det kartesiske kvadrat af toppunktsættet (det vil sige, at hver kant forbinder nøjagtigt to toppunkter).
En graf for slægten g er en graf, der kan afbildes uden skæringspunkter på en overflade af slægten g og ikke kan afbildes uden skæringspunkter på nogen overflade af slægten g -1. Især plane grafer har slægten 0.

D

Dobbelt graf . En graf A kaldes dual til en plan graf B , hvis toppunkterne på graf A svarer til flader på graf B , og to toppunkter på graf A er forbundet med en kant, hvis og kun hvis de tilsvarende flader på graf B har mindst én fælles kant.
En todelt graf (eller bigraf eller en lige graf ) er en graf, således at sættet af toppunkter V er opdelt i to ikke-skærende delmængderog, og enhver kant E falder ind på et toppunkt fraog et toppunkt fra(det vil sige, den forbinder et toppunkt fratil et toppunkt fra). Det vil sige, at den korrekte farvning af grafen udføres med to farver. Mængderneogkaldes "dele" af en todelt graf. En todelt graf kaldes "fuldstændig", hvis to spidser ioger tilstødende. Hvis,, så er den komplette todelte graf betegnet med. $G(V,E)$ $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$ $\left|V_{1}\right|=a$ $\left|V_{2}\right|=b$ $K_{{a,b}}$
En dobbeltforbundet graf er en forbundet graf uden hængsler .
Et træ er en forbundet graf , der ikke indeholder cyklusser .
Grafens diameter er den maksimale afstand mellem toppunkter for alle par af toppunkter. Afstanden mellem toppunkter er det mindste antal kanter i en bane, der forbinder to toppunkter. $\mathrm {diam} (G)$
Rutelængde - antallet af kanter i ruten (med gentagelser) . Hvis ruten er , så er længden af M lig med k (angivet med ). $M=v_{0},e_{1},v_{1},e_{2},v_{2},...,e_{k},v_{k}$ $\venstre|M\højre|=k$
Længden af stien er antallet af buer på stien (eller summen af længderne af dens buer, hvis sidstnævnte er givet). Så for stien v 1 , v 2 , …, v n er længden n-1.
Buen er en orienteret kant .
Et grafkomplement er en graf over det samme sæt af hjørner som den oprindelige, men hjørnerne er forbundet med en kant, hvis og kun hvis der ikke er nogen kant i den originale graf.

E

Blackberry af en urettet graf G er en familie af forbundne undergrafer af grafen G , der er tangent til hinanden.

W

Stjernegrafen er en komplet todelt graf. $K_{{1,b}}$

Og

Et isoleret toppunkt er et toppunkt, hvis grad er 0 (det vil sige, at der ikke er nogen kanter på det).
Isomorfisme . To grafer siges at være isomorfe , hvis der er en permutation af hjørner, således at de er ens. Med andre ord kaldes to grafer isomorfe , hvis der er en en-til-en overensstemmelse mellem deres hjørner og kanter, der bevarer tilstødende og forekomst (grafer adskiller sig kun i navnene på deres hjørner).
En grafinvariant er en numerisk karakteristik af en graf eller deres ordnede vektor, der karakteriserer grafstrukturen ufravigeligt med hensyn til omnummerering af toppunkter.
En intervalgraf er en graf, hvis toppunkter kan tildeles en-til-en til segmenter på den reelle akse på en sådan måde, at to toppunkter falder ind på den samme kant, hvis og kun hvis segmenterne, der svarer til disse toppunkter, skærer hinanden.
Hændelse er et begreb, der kun bruges i forhold til en kant eller en bue og et toppunkt: hvis er toppunkter og a er en kant der forbinder dem, så er toppunktet og kanten indfaldende, og toppunktet og kanten er også indfaldende. To hjørner (eller to kanter) kan ikke være indfaldende. For at betegne de nærmeste hjørner (kanter) bruges begrebet tilstødende . $v_{1},v_{2}$ $e=(v_{1},v_{2})$ $v_{1}$ $e$ $v_{2}$ $e$

K

En celle er en regulær graf over den mindste omkreds for en given grad af hjørner.
En klike er en delmængde af grafens hjørnepunkter, der er fuldstændigt forbundet med hinanden, det vil sige en undergraf, der er en komplet graf .
- Kliknummeret er antallet (G) af hjørner i den største klike . Andre navne er tæthed, tæthed.
- Den maksimale klike er den klike med det maksimalt mulige antal knudepunkter blandt grafens kliker.
Et hjul (betegnet med W n ) er en graf med n toppunkter (n ≥ 4) dannet ved at forbinde et enkelt toppunkt til alle toppunkter i en ( n -1)-cyklus.
Et kogger er blot en rettet graf.
En endelig graf er en graf, der indeholder et begrænset antal hjørner og kanter.
Konstruktiv opregning af grafer - opnåelse af en komplet liste over grafer i en given klasse.
En forbundet komponent af en graf er en delmængde af toppunkterne på grafen , for hvilke som helst to toppunkter, hvoraf der er en sti fra den ene til den anden, og der ikke er nogen sti fra toppunktet af denne delmængde til et toppunkt, der ikke er fra denne delmængde .
En stærkt forbundet komponent i en graf , et lag, er det maksimale sæt af hjørner i en rettet graf , således at der for alle to hjørner fra dette sæt er en sti både fra den første til den anden og fra den anden til den første.
En kontur er en lukket bane i en digraf .
Træets rod er træets valgte node ; i en digraf , et toppunkt med en nulgrad af indtastning.
En cocycle er et minimalt snit , et minimalt sæt kanter, hvis fjernelse gør grafen afbrudt.
Flere kanter er flere kanter , der falder ind i det samme par af hjørner. Findes i multigrafer .
En kubisk graf er en regulær graf af grad 3, det vil sige en graf, hvor nøjagtig tre kanter falder ind på hvert toppunkt.
en k-delt graf er en graf G, hvis kromatiske tal c(G)=k
En k-forbundet graf er en forbundet graf , hvor der ikke er noget sætafeller færre hjørner , således at fjernelse af alle knudepunkter og kanter , der falder ind på dem, bryder grafens sammenhæng. Især er en forbundet graf 1-forbundet, og en dobbeltforbundet graf er 2-forbundet. $V'$ $k-1$ $V'$

L

En Laman-graf med n hjørner er en graf G , således at for det første, for hver k , har enhver undergraf af G , der indeholder k knudepunkter, højst 2 k − 3 kanter, og for det andet har graf G nøjagtigt 2 n −3 kanter.

Skoven er en urettet graf uden cyklusser. Træer er forbindelseskomponenterne i en skov .
Et træblad er et trætop med en enkelt kant eller indgående bue .
Den lokale grad af et toppunkt er antallet af kanter, der falder ind på det. Sløjfen bidrager med "2" til graden af toppunktet.

M

Maxi-kode er en svær at beregne komplet grafinvariant opnået ved at skrive de binære værdier af tilstødende matrix ud i en linje, efterfulgt af at konvertere det resulterende binære tal til decimalform. Maxi-koden svarer til en sådan rækkefølge af rækker og kolonner, hvor den resulterende værdi er den maksimalt mulige. $\mu _{maks.}$
Den maksimale matchning i grafen. En matchning kaldes maksimal, hvis enhver anden matchning har færre kanter.
En rute i en graf er en vekslende sekvens af hjørner og kanter , hvori to tilstødende elementer er indfaldende . Hvis , så er ruten lukket , ellers er den åben . $v_{0},e_{1},v_{1},e_{2},v_{2},...,e_{k},v_{k}$ $v_{0}=v_{k}$
En digrafs tilgængelighedsmatrix er en matrix, der indeholder information om eksistensen af stier mellem hjørner i en digraf.
Incidensmatricen af en graf er en matrix, hvis elementværdier er karakteriseret ved forekomsten af de tilsvarende hjørner af grafen (lodret) og dens kanter (vandret). For en urettet graf tager et element værdien 1 , hvis dets tilsvarende toppunkt og kant er indfaldende. For en rettet graf tager elementet værdien 1 hvis det indfaldende toppunkt er begyndelsen af en kant, værdien -1 hvis det indfaldende toppunkt er slutningen af en kant; i andre tilfælde (inklusive for loops ) tildeles værdien af elementet 0 .
En grafs tilstødende matrix er en matrix, hvis elementværdier er kendetegnet ved tilgrænsende af grafens hjørnepunkter. I dette tilfælde tildeles værdien af matrixelementet antallet af kanter, der forbinder de tilsvarende toppunkter (det vil sige, som falder ind i begge toppunkter).
Mini-kode er en svær at beregne fuld grafinvariant opnået ved at skrive de binære værdier af tilstødende matrix ud i en linje og derefter konvertere det resulterende binære tal til decimalform. Mini-kode svarer til en sådan rækkefølge af rækker og kolonner, hvor den resulterende værdi er den mindst mulige. $\mu _{min}$
Minimumsramme (eller minimumvægtramme , minimumspændende træ ) af en graf er et acyklisk (uden cyklus) sæt kanter i en forbundet, vægtet og ikke-rettet graf, der forbinder alle hjørnerne af denne graf, mens summen af vægtene af alle kanter i den er minimal.
Adjacency-sættet af et toppunkt v er sættet af toppunkter, der støder op til toppunktet v . Udpeget . $\Gamma ^{+}(v)$
En mindre graf er en graf, der kan hentes fra den originale graf ved at fjerne og trække buer sammen.
En bro er en kant , hvis fjernelse øger antallet af forbundne komponenter i grafen.
En multigraf er en graf, hvor der kan være et par hjørner, der er forbundet med mere end én kant (urettet), eller mere end to buer i modsatte retninger.

H

En rettet graf er en rettet graf , hvor to spidser er forbundet med højst en bue.
- En rettet acyklisk graf er en rettet graf uden konturer .
Et uafhængigt toppunktssæt (også kendt som et internt stabilt sæt ) er et toppunktsæt af en graf G, hvor to vilkårlige hjørner ikke støder op til hinanden (intet par af spidser er forbundet med en kant).
- Et uafhængigt sæt kaldes maksimalt , når der ikke er noget andet uafhængigt sæt, som det ville være inkluderet i. Komplementet af det største uafhængige sæt kaldes grafens minimum toppunktsdækning .
- Det største uafhængige sæt er det største uafhængige sæt.
Uafhængige hjørner er parvise ikke-tilstødende hjørner af grafen. [en]
En uadskillelig graf er en forbundet, ikke-tom graf uden artikulationspunkter. [2] .
En normeret graf er en rettet graf uden cyklusser .

En nul-graf ( en tom graf ) er en graf uden hjørner .

Åh

Omkreds er længden af den mindste cyklus i grafen.
Foreningen af grafer (mærkede graferog) er en graf,hvis toppunkt er, og kantsættet er. $G_{1}=(X_{1},U_{1})$ $G_{2}=(X_{2},U_{2})$ $G_{1}\kop G_{2}$ $X_{1}\kop X_{2}$ $U=U_{1}\kop U_{2}$
Et naboskab af orden k er et sæt toppunkter i en afstand k fra et givet toppunkt v ; nogle gange fortolket bredt som et sæt af hjørner adskilt fra v i en afstand, der ikke er større end k .
Miljøet er et sæt af hjørner, der støder op til det givne.
En digraf , en rettet graf G = (V,E) er et sæt sæt, hvor V er et sæt hjørner (knuder), E er et sæt buer (rettede kanter). En bue er et ordnet par af hjørner (v, w), hvor toppunktet v kaldes begyndelsen og w er slutningen af buen. Vi kan sige, at buen v → w fører fra toppunktet v til toppunktet w, mens toppunktet w støder op til toppunktet v.
Et spændingstræ ( skelet ) af en (urettet) forbundet graf er enhver delvis graf , der er et træ . $G=(V,E)$ $S=(V,T)$
En spændende undergraf er en undergraf, der indeholder alle hjørner.

P

En matching er et sæt af parvise ikke-tilstødende kanter.
En løkke er en kant, hvis begyndelse og slutning er i samme toppunkt.
Skæringspunktet mellem grafer (mærkede graferog) er en graf,hvis toppunkt er, og kantsættet er. $G_{1}=(X_{1},U_{1})$ $G_{2}=(X_{2},U_{2})$ $G_{1}\cap G_{2}$ $X_{1}\cap X_{2}$ $U=U_{1}\cap U_{2}$
Grafopregning - optælling af antallet af ikke-isomorfe grafer i en given klasse (med givne karakteristika).
Et perifert toppunkt er et toppunkt, hvis excentricitet er lig med diameteren af grafen.
En plan graf er en graf, der kan tegnes ( stables ) på et plan uden at krydse kanter. Det er isomorf til en plan graf, det vil sige, det er en graf med skæringspunkter, men tillader dens plane lægning, derfor kan den adskille sig fra en plan graf ved et billede på et plan. Der kan således være forskel på en plan graf og en plan graf, når den er afbildet på et plan.
En plan graf er en geometrisk graf , hvor to kanter ikke har fælles punkter, bortset fra det toppunkt, der falder ind på dem begge (de skærer ikke hinanden). Det er en stablet graf på flyet.
En undergraf af den originale graf er en graf, der indeholder en bestemt delmængde af hjørner af den givne graf og en bestemt undergruppe af kanter , der falder ind på dem. (jf . sugraph .) Med hensyn til en subgraf kaldes den originale graf en supergraf
En komplet graf er en graf, hvor der for hvert par af toppunkterer en kant, indfaldog indfald(hver toppunkt er forbundet med en kant til ethvert andet toppunkt). $v_{1},v_{2}$ $v_{1}$ $v_{2}$
En komplet grafinvariant er en numerisk karakteristik af en graf eller deres ordnede vektor, hvis værdier er nødvendige og tilstrækkelige til at etablere grafisomorfi .
En komplet todelt graf er en todelt graf , hvor hvert toppunkt i en delmængde er forbundet med en kant til hvert hjørne af en anden delmængde
In- graden i digrafen for et toppunkt er antallet af buer, der kommer ind i toppunktet. Benævnt med , , eller . $v$ $d^{+}(v)$ $\mathrm {deg} ^{+}(v)$ $\mathrm {indeg} (v)$ $d_{t}(v)$
Udgraden i digrafen for et toppunkt er antallet af buer, der udgår fra toppunktet. Benævnt med , , eller . $v$ $d^{-}(v)$ $\mathrm {deg} ^{-}(v)$ $\mathrm {outdeg} (v)$ $d_{o}(v)$
En mærket graf er en graf, hvis hjørner eller buer er tildelt en slags etiket, for eksempel naturlige tal eller symboler i et eller andet alfabet.
En genereret subgraf er en subgraf genereret af et sæt kanter i den originale graf. Den indeholder ikke nødvendigvis alle spidserne i grafen, men disse spidser er forbundet med de samme kanter som i grafen.
Rækkefølgen af grafen er antallet af grafens toppunkter. [3]
En korrekt graffarvning er en farve , således at hver farveklasse er et selvstændigt sæt. Med andre ord, i en korrekt farvning skal to tilstødende hjørner have forskellige farver.
Et produkt af grafer - for givne grafer er et produkt en graf, hvis toppunkter er det kartesiske produkt af de originale grafers toppunkter. $G_{1}=(V_{1},E_{1})$ $G_{2}=(V_{2},E_{2})$ $G=(V,E)$ $V(G)=V_{1}\ gange V_{2}$
En simpel sti er en sti , hvor alle hjørner er forskellige.
En simpel graf er en graf , der ikke har flere kanter eller sløjfer .
En simpel sti er en sti , hvis toppunkter er parvis adskilte [4] . Med andre ord går en simpel vej ikke gennem det samme toppunkt to gange.
- En simpel cyklus er en cyklus , der ikke går gennem det samme toppunkt to gange.
En pseudograf er en graf, der kan indeholde sløjfer og/eller flere kanter.

En tom graf ( nulgraf ) er en graf uden kanter .
En sti er en sekvens af kanter (i en urettet graf) og/eller buer (i en rettet graf), således at enden af en bue (kant) er begyndelsen af en anden bue (kant). Eller en sekvens af hjørner og buer (kanter), hvor hvert element falder sammen med det forrige og det næste [4] . Kan opfattes som et særligt tilfælde af en rute .
En sti i en digraf er en sekvens af hjørner v 1 , v 2 , …, v n , for hvilke der er buer v 1 → v 2 , v 2 → v 3 , …, v n-1 → v n . Denne sti siges at starte ved toppunkt v 1 , passere gennem toppunkter v 2 , v 3 , …, v n-1 , og slutte ved toppunkt v n .

R

Grafens radius er minimum af excentriciteterne af hjørnerne af en forbundet graf; toppen, hvor dette minimum er nået, kaldes den centrale top.
Opdeling af en graf er en repræsentation af den originale graf som et sæt af undergrupper af hjørner i henhold til visse regler.
Det opdelte toppunkt er det samme som hængslet og ledpunktet .
En graf, der udfolder sig , er en funktion defineret på hjørnerne af en rettet graf.
En mærket graf er en graf, for hvilken der er givet et sæt etiketter S, en toppunktsmærkningsfunktion f : A → S og en buemærkningsfunktion g : R → S. Grafisk er disse funktioner repræsenteret ved etiketter på hjørner og buer. Sættet af etiketter kan opdeles i to ikke-overlappende undersæt af topmærker og buemærker.
Et snit er et sæt kanter , hvis fjernelse gør grafen afbrudt .
En rammegraf er en graf, der kan tegnes i et plan på en sådan måde, at en hvilken som helst afgrænset flade er en firkant, og ethvert toppunkt med tre eller færre naboer falder ind i en ubegrænset flade. [5]
Graffarvning er opdelingen af hjørner i sæt (kaldet farver). Hvis der derudover ikke er to tilstødende hjørner, der hører til det samme sæt (det vil sige, at to tilstødende hjørner altid er af forskellig farve), så kaldes en sådan farve regulær.
Afstanden mellem toppunkterne er længden af den korteste kæde (i sti-digrafen), der forbinder de givne toppunkter. Hvis en sådan kæde (sti) ikke eksisterer, antages afstanden at være lig med uendelig.
Et kantdæksel er et sæt grafkanter, således at hvert toppunkt falder ind på mindst én kant fra dette sæt.
Linjegrafen for en urettet graf er en graf, der repræsenterer naboskabet til grafens kanter.
Edge er et grundlæggende koncept. En kant forbinder to hjørner af en graf.
En regulær graf er en graf, hvis grader af alle hjørner er ens. Graden af regularitet er en grafinvariant og er angivet med. Udefineret for uregelmæssige grafer. Regelmæssige grafer udgør en særlig udfordring for mange algoritmer. $r(G)$ $r(G)$
- En almindelig graf af grad 0 ( helt afbrudt graf , tom graf , nul graf ) er en graf uden kanter .

C

En selv-dual graf er en graf, der er isomorf i forhold til dens dobbelte graf .
Et hyperslankt (stjerneformet) træ er et træ, der har et enkelt toppunkt, der er større end 2.
Forbindelse . To hjørner i en graf er forbundet, hvis der er en (simpel) sti, der forbinder dem .
En forbundet graf er en graf, hvor alle toppunkter er forbundet.
Et udsnit af en graf er et sæt kanter, hvis fjernelse deler grafen op i to isolerede undergrafer, hvoraf den ene især kan være en triviel graf.
Et netværk er i princippet det samme som en graf , selvom netværk normalt kaldes grafer, hvis hjørner er mærket på en bestemt måde.
- Et rettet netværk er en rettet graf, der ikke indeholder konturer.
Stærk tilslutning . To hjørner i en rettet graf er stærkt forbundet, hvis der er en vej fra den første til den anden og fra den anden til den første.
- En stærkt forbundet digraf er en digraf , hvor alle toppunkter er stærkt forbundet.
Adjacency - et begreb, der bruges i forhold til kun to kanter eller kun to toppunkter : To kanter , der falder ind på et toppunkt, kaldes tilstødende ; to hjørner , der falder ind på den samme kant, kaldes også tilstødende . (jf . Hændelse .)
En blandet graf er en graf, der indeholder både rettede og urettede kanter .
En perfekt matchning er en matchning, der indeholder alle toppunkterne i grafen.
Forbindelsen af to grafer og , som ikke har fælles toppunkter, kaldes en graf . [6] $G_{1}=(V_{1},E_{1})$ $G_{2}=(V_{2},E_{2})$ $G_{1}+G_{2}=(V_{1}\kop V_{2},E_{1}\kop E_{2}\kop V_{1}\gange V_{2}\kop V_{2} \ gange V_{1})$

Det kan ses af definitionen, at forbindelsen af grafer har egenskaberne kommutativitet og associativitet

Spektret af en graf er sættet af alle egenværdier af tilstødende matrix, under hensyntagen til flere kanter.
Graden af toppunktet er antallet af kanter på grafen G , der falder ind på toppunktet x . Udpeget. Minimumsgraden af et toppunkt i en graf G er angivet med. og maksimum er. $d(x)$ $\delta (G)$ $\Delta (G)$
Sammentrækning af kanten af grafen - udskiftning af enderne af kanten med et toppunkt, naboerne til disse ender bliver naboerne til det nye toppunkt. Grafen kan trækkes sammen ,hvis den anden kan opnås fra den første ved en sekvens af kantsammentrækninger. $G_{1}$ $G_{2}$
En undergraf ( delgraf ) af den originale graf er en graf, der indeholder alle hjørnerne af den originale graf og en delmængde af dens kanter . (jf . underafsnit .)
Supergraf - enhver graf, der indeholder den originale graf (det vil sige, for hvilken den originale graf er en undergraf )

T

Theta-graf er en graf, der består af foreningen af tre stier, der ikke har fælles hjørnepunkter indeni, og som har samme endespidser [7]
Thetagrafen for et sæt punkter i det euklidiske plan er konstrueret som et system af kegler, der omgiver hvert toppunkt med en kant for hver kegle tilføjet til punktet af sættet, hvis projektion på keglens centrale akse er minimal.

En identitetsgraf er en graf, hvor kun én automorfi er mulig - . Billedligt talt er identitetsgrafen en "absolut ikke-symmetrisk" graf.
Ledningspunktet er det samme som hængslet og delespidsen .
Overfladetriangulering - at lægge en graf på en overflade , opdele den i trekantede områder; et særligt tilfælde af topologisk triangulering .
En triviel graf er en graf, der højst har et toppunkt .
En turnering er en rettet graf , hvor hvert par hjørner er forbundet med en enkelt kant.

Wu

En node er det samme som en vertex .
Stabling , eller grafindlejring : en graf stables på en overflade, hvis den kan tegnes på denne overflade, så grafens kanter ikke skærer hinanden. (Se Plan graf , Plan graf .)
Et shelter er en bestemt type funktion på toppunkterne i en urettet graf. Hvis der er dækning, kan det bruges af flygtningen til at vinde jagt-unddragelse-spillet på grafen ved at bruge denne funktion på hvert trin af spillet til at bestemme sikre sæt hjørner at gå til.
En ordnet graf er en graf, hvor kanterne, der udgår fra hvert toppunkt, er unikt nummererede, startende fra 1. Kanterne anses for at være ordnet i stigende rækkefølge af tal. I grafisk repræsentation anses kanter ofte for at være ordnet i rækkefølgen af en eller anden standardgennemgang (for eksempel mod uret ).

F

n-faktoren for en graf er en regulær spændende undergraf af grad . $n$
n-faktorisering af en graf - opdeling af en graf i uafhængige n-faktorer .

X

Det kromatiske antal af en graf er det mindste antal farver, der kræves for at farve toppunkterne på en graf, således at alle hjørner forbundet med en kant har forskellige farver.
Det karakteristiske polynomium i en graf er det karakteristiske polynomium for dens tilstødende matrix .

C

Centrum af grafen er det sæt af hjørner, for hvilke ligheden er sand:, hvor er toppunktets excentricitet og er grafens radius. $W=\venstre\{u_{1},u_{2},...,u_{n}\right\}$ $\forall i=1,...,n:\varepsilon (u_{i})=r(G)$ $\varepsilon$ $r$
En kæde i en graf er en rute , hvis kanter er forskellige. Hvis alle hjørnerne (og dermed kanterne) er forskellige, så kaldes en sådan kæde simpel ( elementær ). I en kæde kaldes hjørnerne og kædens ender . En kæde med enderne u og v forbinder hjørnerne u og v . Kæden, der forbinder hjørnerne u og v , er betegnet med . For digrafer kaldes en kæde en orkæde. $v_{0},e_{1},...,e_{k},v_{k}$ $v_{0}$ $v_{k}$ $\venstre\langle u,v\højre\rangle$ I nogle kilder er en simpel kæde en kæde, hvis kanter er tydelige, hvilket er en svagere tilstand.
Cyklussen er et lukket kredsløb . For digrafer kaldes en cyklus en kontur .
- En cyklus ( simpel cyklus ) i en digraf er en simpel sti med en længde på mindst 1, der starter og slutter ved samme toppunkt.
- Hamilton-cyklussen er den samme som Hamilton-cyklen .
Det cyklomatiske antal af en graf er det mindste antal kanter, der skal fjernes for at gøre grafen acyklisk . For en forbundet graf er der en sammenhæng:hvor er det cyklomatiske tal, er antallet af forbundne komponenter i grafen, er antallet af kanter og er antallet af hjørner . $p_{1}(G)=p_{0}(G)+|E(G)|-|V(G)|,$ $p_{1}(G)$ $p_{0}$ $|E(G)|$ $|V(G)|$

H

En delvis graf er det samme som en sugraf .
En lige graf er det samme som en todelt graf .
Vertex cover number — størrelsen på det mindste toppunktsdæksel i grafen.
Uafhængighedstallet er størrelsen af det største uafhængige sæt af hjørner i grafen.
Matchende nummer er størrelsen af den største matchning i grafen.
Kantdækselnummer — størrelsen på det mindste kantdæksel i grafen.

W

Et hængsel er et toppunkt af en graf , som et resultat af hvilket, sammen med alle de kanter , der falder ind på den,antallet af forbundne komponenter i grafen stiger som følge af dens fjernelse.
Et tandhjul (betegnet med ) er en graf, der er opnået fra et hjul ved at placere yderligere spidser mellem hvert par af tilstødende spidser af omkredsen . Gears tilhører familien af rammegrafer og spiller en vigtig rolle i beskrivelsen af forbudte undergrafer af rammegrafer [8] $G_{n}$

E

En Euler-graf er en graf, hvor der er en cyklus, der indeholder alle grafens kanter én gang (hjørnerne kan gentages).
Euler-kæde (eller Euler-cyklus ) - en kæde ( cyklus ), der indeholder alle grafens kanter (hjørnepunkter kan gentages).
Excentriciteten af et toppunkt er maksimum af alle minimumsafstandene fra andre toppunkter til et givet toppunkt.
En elementær sti er en sti, hvis toppunkter, med mulig undtagelse af den første og den sidste, er forskellige. En simpel sti går med andre ord ikke gennem det samme toppunkt to gange, men kan starte og slutte ved samme toppunkt, i så fald kaldes det en cyklus (elementær cyklus).
Følgende procedure kaldes elementær kontraktion : vi tager en kant (sammen med de hjørner , der falder ind på den , for eksempel u og v) og "kontrakter" den, det vil sige, vi fjerner kanten og identificerer hjørnerne u og v. Toppunktet opnået på denne måde er indfaldende til de kanter (andre end), som u eller v oprindeligt faldt ind til.

Litteratur

Distel R. Grafteori Pr. fra engelsk. - Novosibirsk: Matematisk Instituts Publishing House, 2002. - 336 s.
Harari F. Grafteori. — M .: URSS , 2003. — 300 s. — ISBN 5-354-00301-6 .

Ordliste over grafteori

En

B

I

G

D

E

W

Og

K

L

M

H

Åh

P

R

C

T

Wu

F

X

C

H

W

E

Links

Litteratur