Ordlista för grafteori

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 17 augusti 2022; kontroller kräver 2 redigeringar .

Här finns samlade definitioner av termer från grafteorin . Referenser till termer i denna ordbok (på denna sida) är kursiverade .

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

En

Automorfism - En isomorfism av en graf med sig själv.
En acyklisk graf är en graf utan cykler .

B

En grafbas är en minimal delmängd av uppsättningen av grafens hörn från vilken varje grafhörn kan nås.
En oändlig graf är en graf som har oändligt många hörn och/eller kanter.
Bigraf - se tvådelad graf .
Ett block är en graf utan gångjärn .
Blockdesign med parametrar (v, k, λ) är en täckning med multiplicitet λ av en komplett graf på v hörn med kompletta grafer på k hörn.

I

Vertex valens - se vertex grad .
Vertex , nod - grundläggande koncept : en punkt där kanter och / eller bågar kan konvergera / gå ur. Uppsättningen av hörn i en graf G betecknas med V(G).
Ett vertextäcke är en uppsättning av hörn i en graf så att varje kant faller in mot åtminstone en vertex från denna uppsättning.
Vikten av en kant är det värde som tilldelas en given kant på en viktad graf . Vanligtvis är vikten ett reellt tal , i vilket fall det kan tolkas som " längden " på kanten.
En viktad graf är en graf , vars varje kant tilldelas ett visst värde ( kantvikt ). Se märkt graf .
En hängande vertex är en vertex vars grad är lika med 1 (det vill säga ). $d(v)=1$

En helt frånkopplad graf är en vanlig graf av grad 0, det vill säga en graf utan kanter .
Höjden på ett träd är den längsta vägen från roten till bladet .

G

En Hamiltonsk graf är en graf som har en Hamiltonsk cykel .
En Hamiltonsk bana är en enkel bana i en graf som innehåller alla hörn i grafen exakt en gång.
En Hamiltonsk cykel är en enkel cykel i en graf som innehåller alla hörn i grafen exakt en gång.
En geometrisk realisering är en figur vars hörn motsvarar grafens hörn, kanter - kanterna på grafen och kanterna i figuren förbinder de hörn som motsvarar hörnen i grafen.
En geometrisk graf är en platt figur av hörn - punkter i planet och kanter - linjer som förbinder några par av hörn. Kan representera vilken graf som helst på många sätt.
En hypergraf är en samling av en uppsättning hörn och en uppsättning hyperkanter (en delmängd av den n:te euklidiska potensen av uppsättningen av hörn, det vill säga hyperkanter förbinder ett godtyckligt antal hörn).
Homeomorfa grafer är grafer som erhålls från en enda graf med hjälp av en sekvens av kantuppdelningar.
En yta är ett område som begränsas av kanter i en plan graf och innehåller inte grafens hörn och kanter. Den yttre delen av planet bildar också ett ansikte.
Graf är ett grundbegrepp. Inkluderar en vertexmängd och en kantmängd som är en delmängd av den kartesiska kvadraten av vertexmängden (det vill säga varje kant förbinder exakt två hörn).
En graf av släktet g är en graf som kan avbildas utan skärningar på en yta av släktet g och inte kan avbildas utan skärningar på någon yta av släktet g -1. Speciellt plana grafer har släktet 0.

D

Dubbel graf . En graf A kallas dubbel till en plan graf B om hörnen på graf A motsvarar ytorna på graf B och två hörn på graf A är förbundna med en kant om och endast om motsvarande ytor på graf B har minst en gemensam kant.
En tvådelad graf (eller bigraf , eller en jämn graf ) är en grafså att uppsättningen av hörn V är uppdelad i två icke-korsande delmängderoch, och varje kant E faller in mot en vertex frånoch en vertex från(det vill säga, den förbinder en vertex fråntill en vertex från). Det vill säga, korrekt färgning av grafen utförs med två färger. Mängdernaochkallas "delar" av en tvådelad graf. En tvådelad graf kallas "fullständig" om några två hörn iochär intill varandra. Om,, så betecknas hela tvådelade grafen 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 dubbelkopplad graf är en sammankopplad graf som inte har några gångjärn .
Ett träd är en sammankopplad graf som inte innehåller cykler .
Diametern är det maximala avståndet mellan hörn för alla par av hörn. Avståndet mellan hörn är det minsta antalet kanter i en bana som förbinder två hörn. $\mathrm {diam} (G)$
Ruttens längd - antalet kanter i rutten (med upprepningar). Om rutten är , är längden på M lika med k (betecknad med ). $M=v_{0},e_{1},v_{1},e_{2},v_{2},...,e_{k},v_{k}$ $\vänster|M\höger|=k$
Banans längd är antalet bågar av banan (eller summan av längderna av dess bågar, om de senare anges). Så för banan v 1 , v 2 , …, v n är längden n-1.
Bågen är en orienterad kant .
Ett grafkomplement är en graf över samma uppsättning hörn som den ursprungliga, men hörnen är sammankopplade med en kant om och bara om det inte finns någon kant i den ursprungliga grafen.

E

Blackberry av en oriktad graf G är en familj av sammankopplade subgrafer av grafen G som tangerar varandra.

W

Stjärngrafen är en komplett tvådelad graf. $K_{{1,b}}$

Och

En isolerad vertex är en vertex vars grad är 0 (det vill säga det finns inga kanter som faller in på den).
Isomorfism . Två grafer sägs vara isomorfa om det finns en permutation av hörn så att de är lika. Med andra ord kallas två grafer isomorfa om det finns en en-till-en-överensstämmelse mellan deras hörn och kanter som bevarar närliggande och incidens (grafer skiljer sig endast i namnen på deras hörn).
En grafinvariant är en numerisk egenskap hos en graf eller deras ordnade vektor som karakteriserar grafstrukturen oföränderligt med avseende på omnumrering av hörn.
En intervallgraf är en graf vars hörn kan tilldelas en-till-en till segment på den reella axeln på ett sådant sätt att två hörn faller in mot samma kant om och endast om segmenten som motsvarar dessa hörn skär varandra.
Incident är ett begrepp som endast används i förhållande till en kant eller en båge och en vertex: om är hörn och a är en kant som förbinder dem, då är vertex och kant infallande, och vertex och kant är också infallande. Två hörn (eller två kanter) kan inte vara infallande. För att beteckna de närmaste hörnen (kanterna) används begreppet närliggande . $v_{1},v_{2}$ $e=(v_{1},v_{2})$ $v_{1}$ $e$ $v_{2}$ $e$

K

En cell är en vanlig graf över den minsta omkretsen för en given grad av hörn.
En klick är en delmängd av grafens hörn som är helt kopplade till varandra, det vill säga en subgraf som är en komplett graf .
- Klicknumret är antalet (G) hörn i den största klicken . Andra namn är densitet, densitet.
- Den maximala klicken är klicken med det maximala antalet hörn bland grafens klick.
Ett hjul (betecknat med W n ) är en graf med n hörn (n ≥ 4) bildad genom att koppla en enda vertex till alla hörn i en ( n -1)-cykel.
Ett koger är bara en riktad graf.
En finit graf är en graf som innehåller ett begränsat antal hörn och kanter.
Konstruktiv uppräkning av grafer - få en komplett lista över grafer i en given klass.
En sammankopplad komponent i en graf är en delmängd av grafens hörn , för vilka två hörn det finns en väg från den ena till den andra, och det inte finns någon väg från denna delmängds hörn till en vertex som inte kommer från denna delmängd .
En starkt sammankopplad komponent i en graf , ett lager är den maximala uppsättningen av hörn i en riktad graf , så att det för två av dessa hörn finns en väg både från den första till den andra och från den andra till den första.
En kontur är en stängd bana i en digraf .
Trädets rot är den valda noden i trädet ; i en digraf , en vertex med en nollgrad av inträde.
En samcykel är ett minimalt snitt , en minimal uppsättning kanter, vars borttagning gör att grafen kopplas bort.
Flera kanter är flera kanter som faller in mot samma par av hörn. Finns i multigrafer .
En kubisk graf är en vanlig graf av grad 3, det vill säga en graf där exakt tre kanter faller in mot varje vertex.
en k-partit graf är en graf G vars kromatiska tal c(G)=k
En k-kopplad graf är en sammankopplad graf där det inte finns någon uppsättningellerfärre hörn så att om du tar bort alla hörn och kanter som faller på dembryter sammankopplingen av grafen. I synnerhet är en sammankopplad graf 1-kopplad och en dubbelkopplad graf är 2-kopplad. $V'$ $k-1$ $V'$

L

En Laman-graf med n hörn är en graf G så att, för det första, för varje k , varje subgraf av G som innehåller k hörn har högst 2 k − 3 kanter och, för det andra, graf G har exakt 2 n −3 kanter.

Skogen är en oriktad graf utan cykler. Träd är kopplingskomponenterna i en skog .
Ett trädblad är ett trädspunkt med en enda kant eller inkommande båge .
Den lokala graden av en vertex är antalet kanter som faller in på den. Slingan bidrar med "2" till graden av vertex.

M

Maxi-kod är en svårberäknad komplett grafinvariant som erhålls genom att skriva ut de binära värdena för närliggande matris på en linje, följt av att konvertera det resulterande binära talet till decimalform. Maxkoden motsvarar en sådan ordning av rader och kolumner, där det resulterande värdet är det maximala möjliga. $\mu _{max}$
Maximal matchning i grafen. En matchning kallas maximal om någon annan matchning har färre kanter.
En rutt i en graf är en alternerande sekvens av hörn och kanter där två intilliggande element faller in . Om , då är rutten stängd , annars är den öppen . $v_{0},e_{1},v_{1},e_{2},v_{2},...,e_{k},v_{k}$ $v_{0}=v_{k}$
Nåbarhetsmatrisen för en digraf är en matris som innehåller information om förekomsten av vägar mellan hörn i en digraf.
Incidensmatrisen för en graf är en matris vars elementvärden kännetecknas av förekomsten av motsvarande hörn i grafen (vertikalt) och dess kanter (horisontellt). För en oriktad graf tar ett element värdet 1 om dess motsvarande vertex och kant är infallande. För en riktad graf tar elementet värdet 1 om den infallande vertexen är början på en kant, värdet -1 om den infallande vertexen är slutet av en kant; i andra fall (inklusive för loopar ) tilldelas elementets värde 0 .
Närliggande matris för en graf är en matris vars elementvärden kännetecknas av närliggande grafens hörn. I detta fall tilldelas värdet på matriselementet antalet kanter som förbinder motsvarande hörn (det vill säga som faller in i båda hörnen).
Minikod är en svårberäknad full grafinvariant som erhålls genom att skriva ut de binära värdena för närliggande matris till en linje och sedan konvertera det resulterande binära talet till decimalform. Minikod motsvarar en sådan ordning av rader och kolumner, där det resulterande värdet är det minsta möjliga. $\mu _{min}$
Minsta ram (eller minimiviktsram , minsta spännträd ) för en graf är en acyklisk (utan cykler) uppsättning kanter i en sammankopplad, viktad och oriktad graf som förbinder alla hörn i denna graf, medan summan av vikterna av alla kanterna i den är minimala.
Adjacency-mängden för en vertex v är mängden av hörn som gränsar till vertex v . Utsedda . $\Gamma ^{+}(v)$
En mollgraf är en graf som kan erhållas från den ursprungliga grafen genom att ta bort och dra ihop bågar.
En bro är en kant vars borttagning ökar antalet anslutna komponenter i grafen.
En multigraf är en graf där det kan finnas ett par hörn som är förbundna med mer än en kant (oriktad), eller mer än två bågar i motsatta riktningar.

H

En riktad graf är en riktad graf där två hörn är sammankopplade med högst en båge.
- En riktad acyklisk graf är en riktad graf utan konturer .
En oberoende vertexuppsättning (även känd som en internt stabil uppsättning ) är en vertexuppsättning av en graf G där två av de hörn som helst inte är intill varandra (inget par av hörn är förbundna med en kant).
- En oberoende mängd kallas maximal när det inte finns någon annan oberoende mängd som den skulle ingå i. Komplementet av den största oberoende uppsättningen kallas grafens minsta vertextäckning .
- Den största oberoende uppsättningen är den största oberoende uppsättningen.
Oberoende hörn är parvisa icke-angränsande hörn i grafen. [ett]
En oskiljaktig graf är en sammankopplad, icke-tom graf utan artikulationspunkter. [2] .
En normerad graf är en riktad graf utan cykler .

En nollgraf ( en tom graf ) är en graf utan hörn .

Åh

Omkretsen är längden på den minsta cykeln i grafen.
Unionen av grafer (märkta graferoch) är en grafvars vertexuppsättning är, och kantuppsättningen är. $G_{1}=(X_{1},U_{1})$ $G_{2}=(X_{2},U_{2})$ $G_{1}\kopp G_{2}$ $X_{1}\kopp X_{2}$ $U=U_{1}\kopp U_{2}$
En grannskap av ordningen k är en uppsättning av hörn på ett avstånd k från en given vertex v ; ibland tolkas brett som en uppsättning hörn separerade från v på ett avstånd som inte är större än k .
Miljön är en uppsättning hörn som gränsar till den givna.
En digraf , en riktad graf G = (V,E) är ett par uppsättningar, där V är en uppsättning av hörn (noder), E är en uppsättning bågar (riktade kanter). En båge är ett ordnat par av hörn (v, w), där hörnet v kallas början och w är slutet på bågen. Vi kan säga att bågen v → w leder från spetsen v till spetsen w, medan spetsen w ligger intill spetsen v.
Ett spännträd ( skelett ) av en (oriktad) sammankopplad graf är vilken partiell graf som helst som är ett träd . $G=(V,E)$ $S=(V,T)$
En spännande subgraf är en subgraf som innehåller alla hörn.

P

En matchning är en uppsättning av parvisa icke intilliggande kanter.
En slinga är en kant vars början och slut är i samma vertex.
Skärningspunkten mellan grafer (märkta graferoch) är en grafvars vertexuppsättning är, och kantuppsättningen är. $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}$
Grafuppräkning - räknar antalet icke-isomorfa grafer i en given klass (med givna egenskaper).
En perifer vertex är en vertex vars excentricitet är lika med diametern på grafen.
En plan graf är en graf som kan ritas ( staplas ) på ett plan utan att korsa kanter. Det är isomorft till en plan graf, det vill säga det är en graf med skärningspunkter, men tillåter dess plana läggning, därför kan den skilja sig från en plan graf genom en bild på ett plan. Således kan det finnas en skillnad mellan en plan graf och en plan graf när den avbildas på ett plan.
En plan graf är en geometrisk graf där inga två kanter har gemensamma punkter, förutom den vertex som faller in på dem båda (de skär inte varandra). Det är en staplad graf på planet.
En subgraf av den ursprungliga grafen är en graf som innehåller en viss delmängd av hörn i den givna grafen och en viss delmängd av kanter som faller in på dem. (jfr sugraph .) När det gäller en subgraf kallas den ursprungliga grafen en supergraf
En komplett graf är en graf där det för varje par av hörnfinns en kant, infallandeoch infallande(varje hörn är ansluten med en kant till någon annan vertex). $v_{1},v_{2}$ $v_{1}$ $v_{2}$
En komplett grafinvariant är en numerisk egenskap hos en graf eller deras ordnade vektor, vars värden är nödvändiga och tillräckliga för att etablera grafisomorfism .
En komplett tvådelad graf är en tvådelad graf där varje hörn i en delmängd är ansluten med en kant till varje hörn i en annan delmängd
Graden i digrafen för en vertex är antalet bågar som kommer in i vertexet. Betecknas med , , eller . $v$ $d^{+}(v)$ $\mathrm {deg} ^{+}(v)$ $\mathrm {indeg} (v)$ $d_{t}(v)$
Utgraden i digrafen för en vertex är antalet bågar som utgår från vertexen. Betecknas med , , eller . $v$ $d^{-}(v)$ $\mathrm {deg} ^{-}(v)$ $\mathrm {outdeg} (v)$ $d_{o}(v)$
En märkt graf är en graf vars hörn eller bågar är tilldelade någon slags etikett, till exempel naturliga tal eller symboler i något alfabet.
En genererad subgraf är en subgraf som genereras av en uppsättning kanter i den ursprungliga grafen. Den innehåller inte nödvändigtvis alla hörn i grafen, men dessa hörn är förbundna med samma kanter som i grafen.
Ordningen på grafen är antalet grafens hörn. [3]
En korrekt graffärgning är en färgning så att varje färgklass är en oberoende uppsättning. Med andra ord, i en korrekt färgning måste två intilliggande hörn ha olika färger.
En produkt av grafer - för givna grafer är en produkt en graf vars hörn är den kartesiska produkten av uppsättningarna av hörn i de ursprungliga graferna. $G_{1}=(V_{1},E_{1})$ $G_{2}=(V_{2},E_{2})$ $G=(V,E)$ $V(G)=V_{1}\ gånger V_{2}$
En enkel väg är en väg där alla hörn är distinkta.
En enkel graf är en graf som inte har flera kanter eller slingor .
En enkel väg är en väg vars alla hörn är parvis distinkta [4] . Med andra ord, en enkel väg går inte genom samma vertex två gånger.
- En enkel cykel är en cykel som inte går genom samma vertex två gånger.
En pseudograf är en graf som kan innehålla slingor och/eller flera kanter.

En tom graf ( nollgraf ) är en graf utan kanter .
En bana är en sekvens av kanter (i en oriktad graf) och/eller bågar (i en riktad graf), så att slutet av en båge (kant) är början på en annan båge (kant). Eller en sekvens av hörn och bågar (kanter), där varje element faller samman med föregående och nästa [4] . Kan ses som ett specialfall av en rutt .
En bana i en digraf är en sekvens av hörn v 1 , v 2 , …, v n , för vilka det finns bågar v 1 → v 2 , v 2 → v 3 , …, v n-1 → v n . Denna väg sägs börja vid vertex v 1 , passera genom vertex v 2 , v 3 , …, v n-1 , och sluta vid toppunkt v n .

R

Grafradien är minimum av excentriciteterna hos hörnen i en sammankopplad graf; toppen vid vilken detta minimum uppnås kallas den centrala toppen.
Att dela upp en graf är en representation av den ursprungliga grafen som en uppsättning delmängder av hörn enligt vissa regler.
Den delade vertexen är samma som gångjärnet och artikulationspunkten .
En graf som vecklas ut är en funktion som definieras på hörnen av en riktad graf.
En märkt graf är en graf för vilken en uppsättning etiketter S, en vertexmärkningsfunktion f : A → S och en bågmärkningsfunktion g : R → S ges. Grafiskt representeras dessa funktioner av etiketter på hörn och bågar. Uppsättningen av etiketter kan delas upp i två icke-överlappande delmängder av vertexetiketter och bågetiketter.
Ett snitt är en uppsättning kanter , vars borttagning gör att grafen kopplas bort .
En ramgraf är en graf som kan ritas i ett plan på ett sådant sätt att vilken avgränsad yta som helst är en fyrhörning och vilken vertex som helst med tre eller färre grannar faller in mot en obegränsad yta. [5]
Graffärgning är uppdelningen av hörn i mängder (kallade färger). Om det dessutom inte finns två angränsande hörn som hör till samma uppsättning (det vill säga två angränsande hörn är alltid av olika färg), så kallas en sådan färgning regelbunden.
Avståndet mellan hörnen är längden på den kortaste kedjan (i vägdigrafen) som förbinder de givna hörnen. Om en sådan kedja (bana) inte existerar, antas avståndet vara lika med oändligheten.
Ett kantskydd är en uppsättning grafkanter så att varje vertex faller in mot åtminstone en kant från denna uppsättning.
Linjediagrammet för en oriktad graf är en graf som representerar närheten av grafens kanter.
Edge är ett grundbegrepp. En kant förbinder två hörn i en graf.
En vanlig graf är en graf vars grader av alla hörn är lika. Graden av regularitet är engrafinvariant och betecknas med . Odefinierat för oregelbundna grafer. Regelbundna grafer utgör en särskild utmaning för många algoritmer. $r(G)$ $r(G)$
- En vanlig graf av grad 0 ( helt bortkopplad graf , tom graf , nollgraf ) är en graf utan kanter .

C

En självdubbel graf är en graf som är isomorf till sin dubbla graf .
Ett hyperslankt (stjärnformat) träd är ett träd som har en enda vertex som är större än 2.
Anslutningar . Två hörn i en graf är sammankopplade om det finns en (enkel) bana som förbinder dem .
En sammankopplad graf är en graf där alla hörn är sammankopplade.
En sektion av en graf är en uppsättning kanter vars borttagning delar upp grafen i två isolerade subgrafer, varav en i synnerhet kan vara en trivial graf.
Ett nätverk är i princip detsamma som en graf , även om nätverk brukar kallas för grafer vars hörn är märkta på ett visst sätt.
- Ett riktat nätverk är en riktad graf som inte innehåller konturer.
Stark anslutning . Två hörn i en riktad graf är starkt sammankopplade om det finns en väg från den första till den andra och från den andra till den första.
- En starkt ansluten digraf är en digraf där alla hörn är starkt anslutna.
Adjacency - ett begrepp som används i förhållande till endast två kanter eller endast två hörn : Två kanter som faller in på en vertex kallas angränsande ; två hörn som faller in på samma kant kallas också angränsande . (jfr Incident .)
En blandad graf är en graf som innehåller både riktade och oriktade kanter .
En perfekt matchning är en matchning som innehåller alla hörn i grafen.
Kopplingen av två grafer och , som inte har gemensamma hörn, kallas en graf . [6] $G_{1}=(V_{1},E_{1})$ $G_{2}=(V_{2},E_{2})$ $G_{1}+G_{2}=(V_{1}\kopp V_{2},E_{1}\kopp E_{2}\kopp V_{1}\ gånger V_{2}\kopp V_{2} \times V_{1})$

Det kan ses av definitionen att kopplingen av grafer har egenskaperna kommutativitet och associativitet

Spektrum för en graf är uppsättningen av alla egenvärden för närliggande matris, med hänsyn till flera kanter.
Graden av vertex är antalet kanter på grafen G som faller in mot vertexen x . Utsedda. Den minsta graden av en vertex i en graf G betecknas med. och det maximala är. $d(x)$ $\delta (G)$ $\Delta (G)$
Sammandragning av grafens kant - ersättning av kantens ändar med en vertex, grannarna till dessa ändar blir grannar till den nya vertexen. Grafen är sammandragbar tillom den andra kan erhållas från den första genom en sekvens av kantsammandragningar. $G_{1}$ $G_{2}$
En subgraf ( delgraf ) av den ursprungliga grafen är en graf som innehåller alla hörn i den ursprungliga grafen och en delmängd av dess kanter . (jfr understycke .)
Supergraph - vilken graf som helst som innehåller den ursprungliga grafen (det vill säga för vilken den ursprungliga grafen är en subgraf )

T

Theta-graf är en graf som består av föreningen av tre banor som inte har gemensamma hörn inuti, och som har samma ändpunkter [7]
Thetagrafen för en uppsättning punkter i det euklidiska planet är konstruerad som ett system av koner som omger varje vertex med en kant för varje kon adderad till den punkt av uppsättningen vars projektion på konens centrala axel är minimal.

En identitetsgraf är en graf för vilken endast en automorfism är möjlig - . Figurativt sett är identitetsgrafen en "absolut icke-symmetrisk" graf.
Ledpunkten är densamma som gångjärnet och delningspunkten .
Yttriangulering - lägga en graf på en yta , bryta den i triangulära områden; ett specialfall av topologisk triangulering .
En trivial graf är en graf som har högst en vertex .
En turnering är en riktad graf där varje par hörn är förbundna med en enda kant.

Wu

En nod är detsamma som en vertex .
Stapling , eller grafinbäddning : en graf staplas på någon yta om den kan ritas på denna yta så att grafens kanter inte skär varandra. (Se Planar graph , Planar graph .)
Ett skydd är en viss typ av funktion på vertexuppsättningarna av en oriktad graf. Om täckning finns kan den användas av flyktingen för att vinna jakt-undvikande spelet på grafen genom att använda den här funktionen i varje steg av spelet för att bestämma säkra uppsättningar av hörn att gå till.
En ordnad graf är en graf där kanterna som utgår från varje vertex är unikt numrerade, med början från 1. Kanterna anses vara ordnade i stigande ordningsföljd av siffror. I grafisk representation anses kanter ofta vara ordnade i ordningsföljden för någon standardtraversering (till exempel moturs ).

F

n-faktorn för en graf är en regelbunden spännande subgraf av grad . $n$
n-faktorisering av en graf - dela upp en graf i oberoende n-faktorer .

X

Det kromatiska antalet av en graf är det minsta antal färger som krävs för att färga toppen av en graf så att alla hörn som är förbundna med en kant har olika färger.
Det karakteristiska polynomet i en graf är det karakteristiska polynomet för dess närliggande matris .

C

Mitten av grafen är uppsättningen av hörn, för vilka likheten är sann:, där är excentriciteten för vertexen och är grafens radie. $W=\left\{u_{1},u_{2},...,u_{n}\right\}$ $\forall i=1,...,n:\varepsilon (u_{i})=r(G)$ $\varepsilon$ $r$
En kedja i en graf är en rutt , vars alla kanter är distinkta. Om alla hörn (och därmed kanterna) är olika, kallas en sådan kedja enkel ( elementär ). I en kedja kallas hörnen och kedjans ändar . En kedja med ändarna u och v förbinder hörnen u och v . Kedjan som förbinder hörnen u och v betecknas med . För digrafer kallas en kedja en orkedja. $v_{0},e_{1},...,e_{k},v_{k}$ $v_{0}$ $v_{k}$ $\left\langle u,v\right\rangle$ I vissa källor är en enkel kedja en kedja vars kanter är distinkta, vilket är ett svagare tillstånd.
Cykeln är en sluten krets . För digrafer kallas en cykel en kontur .
- En cykel ( enkel cykel ) i en digraf är en enkel bana med längden minst 1 som börjar och slutar vid samma vertex.
- Hamiltoncykeln är densamma som Hamiltoncykeln .
Det cyklomatiska talet för en graf är det minsta antalet kanter som måste tas bort för att göra grafen acyklisk . För en sammankopplad graf finns det ett samband:var är det cyklomatiska talet, är antalet anslutna komponenter i grafen, är antalet kanter och är antalet hörn . $p_{1}(G)=p_{0}(G)+|E(G)|-|V(G)|,$ $p_{1}(G)$ $p_{0}$ $|E(G)|$ $|V(G)|$

H

En partiell graf är detsamma som en sugraf .
En jämn graf är detsamma som en tvådelad graf .
Vertex cover number — storleken på det minsta vertextäcket i grafen.
Oberoendetalet är storleken på den största oberoende uppsättningen av hörn i grafen.
Matchningstalet är storleken på den största matchningen i grafen.
Kantskyddsnummer — storleken på det minsta kantskyddet i grafen.

W

Ett gångjärn är ett hörn av en graf , som ett resultat av vilket, tillsammans med alla kanter som träffar den,antalet anslutna komponenter i grafen ökar som ett resultat av att den tas bort.
En kugghjul (betecknad med ) är en graf som erhålls från ett hjul genom att placera ytterligare hörn mellan varje par av angränsande hörn av omkretsen . Kugghjul tillhör familjen ramgrafer och spelar en viktig roll i beskrivningen av förbjudna subgrafer av ramgrafer [8] $G_{n}$

E

En Euler-graf är en graf i vilken det finns en cykel som innehåller alla kanterna på grafen en gång (hörnen kan upprepas).
Eulerkedja (eller Eulercykel ) - en kedja ( cykel ) som innehåller alla kanter på grafen (hörn kan upprepas).
Excentriciteten för en vertex är det maximala av alla minimiavstånd från andra hörn till en given vertex.
En elementär väg är en väg vars hörn, möjligen med undantag för den första och sista, är olika. En enkel bana går med andra ord inte genom samma vertex två gånger, utan kan börja och sluta vid samma vertex, i så fall kallas det en cykel (elementär cykel).
Följande procedur kallas elementär kontraktion : vi tar en kant (tillsammans med de hörn som faller på den , till exempel u och v) och "drar ihop" den, det vill säga vi tar bort kanten och identifierar hörnen u och v. Spetsen som erhålls på detta sätt är infallande mot de kanter (annat än) som u eller v ursprungligen inföll.

Länkar

↑ Distel R. Graph Theory Per. från engelska. - Novosibirsk: Publishing House of the Institute of Mathematics, 2002. - S. 17.
↑ Harari F. Grafteori. - M.: Mir, 1972. - S. 41.
↑ Distel R. Graph Theory Per. från engelska. - Novosibirsk: Matematikinstitutets förlag, 2002. - S. 16.
↑ 1 2 Kuznetsov O. P., Adelson-Velsky G. M. / Diskret matematik för en ingenjör. / M .: Energi, 1980-344 s., ill. Sida 120-122
↑ A. V. Karzanov. Utvidgningar av finita mått och problemet med utrustningsplacering // Proceedings of the ISA RAS. - 2007. - T. 29 . - S. 225-244 (241) .
↑ M. B. Abrosimov. På minimal vertex 1-förlängningar av anslutningar av grafer av en speciell form. // Applied Graph Theory - 2011. - Issue. 4 .
↑ JA Bondy. . - Springer, 1972. - T. 303. - S. 43–54. — (Föreläsningsanteckningar i matematik). - doi : 10.1007/BFb0067356 .
↑ H.-J. Bandelt, V. Chepoi, D. Eppstein. Kombinatorik och geometri för finita och oändliga kvadratgrafer // SIAM Journal on Discrete Mathematics . - 2010. - T. 24 , nr. 4 . - S. 1399-1440 . - doi : 10.1137/090760301 . - arXiv : 0905.4537 . .

Litteratur

Distel R. Grafteori Per. från engelska. - Novosibirsk: Publishing House of the Institute of Mathematics, 2002. - 336 s.
Harari F. Grafteori. — M .: URSS , 2003. — 300 sid. — ISBN 5-354-00301-6 .