Ordlista med grafteori - Glossary of graph theory

Detta är en ordlista för grafteori . Grafteori är studiet av grafer , system av noder eller hörn kopplade i par med linjer eller kanter .

Symboler

Hakparentes [ ]
G [ S ] är den inducerade subgraf av en graf G för vertex delmängd S .
Prime symbol '
Den främsta symbolen används ofta för att modifiera notation för diagram invarianter så att det gäller för linjediagram i stället för den givna grafen. Exempelvis är α ( G ) självständighetsnumret för en graf; α ′ ( G ) är grafens matchande nummer, vilket är lika med självständighetsnumret för dess linjediagram. På samma sätt är χ ( G ) det kromatiska talet i en graf; χ  ′ ( G ) är grafens kromatiska index, vilket är lika med det kromatiska antalet för dess linjediagram.

A

absorberande
En absorberande uppsättning av en riktad graf är en uppsättning hörn så att det för en hörnpunkt finns en kant från mot en hörn av .
akromatisk
Det akromatiska antalet i en graf är det maximala antalet färger i en komplett färgning.
acyklisk
1. En graf är acyklisk om den inte har några cykler. En okontrollerad acyklisk graf är samma sak som en skog . Riktade acykliska grafer kallas mindre ofta för acykliskt riktade grafer.
2. En acyklisk färgning av en oriktad graf är en korrekt färgning där varannan färgklass framkallar en skog.
adjacency matris
Den grannmatris av ett diagram är en matris vars rader och kolumner är båda indexeras av hörn i grafen, med en en i cellen för rad i och kolumn j när hörn i och j är angränsande, och en nolla annars.
intilliggande
1. Förhållandet mellan två hörn som båda är slutpunkter på samma kant.
2. Förhållandet mellan två distinkta kanter som delar en ändpunkt.
α
För en graf G är α ( G ) (med den grekiska bokstaven alfa) dess oberoende nummer (se oberoende ), och α ′ ( G ) är dess matchande nummer (se matchning ).
alternerande
I en graf med en matchning är en alternerande väg en väg vars kanter växlar mellan matchade och omatchade kanter. En alternerande cykel är på liknande sätt en cykel vars kanter växlar mellan matchade och omåttliga kanter. En förstärkningsväg är en alternerande väg som börjar och slutar vid omättade hörn. En större matchning kan hittas som den symmetriska skillnaden mellan matchningen och förstärkningsbanan; en matchning är maximal om och bara om den inte har någon förstärkningsväg.
antikedja
I en riktad acyklisk graf , en delmängd S av hörn som är parvis ojämförliga, dvs för någon i S , finns det ingen riktad väg från x till y eller från y till x . Inspirerad av begreppet antikedjor i delvis beställda uppsättningar .
anti-kant
Synonym för icke-kant , ett par icke-intilliggande hörn.
anti-triangel
En oberoende uppsättning med tre vertex, komplementet till en triangel.
apex
1. En spetsgraf är en graf där en toppunkt kan tas bort och lämnar en plan subgraf. Det borttagna hörnet kallas spetsen. En k -apex graf är en graf som kan göras plana genom avlägsnande av k vertex.
2. Synonym för universal vertex , en hörn intill alla andra hörn.
arborescens
Synonym för ett rotat och riktat träd; se träd .
båge
Se kant .
pil
Ett ordnat par av hörn , såsom en kant i en riktad graf . En pil ( x , y ) har en svans x , ett huvud y och en riktning från x till y ; y sägs vara den direkta efterföljaren till x och x den direkta föregångaren till y . Pilen ( y , x ) är pilens inverterade pil ( x , y ) .
artikulationspunkt
En toppunkt i en ansluten graf vars borttagning skulle koppla bort grafen.
-ary
Ett k -ary -träd är ett rotat träd där varje inre toppunkt inte har mer än k -barn. Ett 1-ary-träd är bara en väg. Ett 2-ary-träd kallas också ett binärt träd , även om termen mer korrekt hänvisar till 2-ary-träd där barnen i varje nod skiljer sig som vänster- eller högerbarn (med högst ett av varje typ). Ett k -ary -träd sägs vara komplett om varje inre toppunkt har exakt k -barn.
förstärkning
En speciell typ av alternerande väg; se alternerande .
automorfism
En grafautomorfism är en symmetri av en graf, en isomorfism från grafen till sig själv.

B

väska
En av uppsättningarna hörn i ett trädets sönderdelning .
balanserad
En bipartit eller multipartit graf är balanserad om varje två delmängder av dess toppunkt partition har storlekar inom en av varandra.
bandbredd
Den bandbredd av en graf G är minimum, över alla ordningar av hörn i G , av längden av den längsta sidan (antalet steg i beställnings mellan dess båda ändpunkter). Det är också en mindre än storleken på den maximala klicken i ett korrekt intervall av G , valt för att minimera klickstorleken.
biclique
Synonym för komplett bipartit graf eller komplett bipartite subgraf; se komplett .
ansluten
Vanligtvis en synonym för 2 -vertex-ansluten , men inkluderar ibland K 2 även om den inte är 2-ansluten. Se ansluten ; för komponenter som är sammankopplade , se komponent .
bindande nummer
Det minsta möjliga förhållandet mellan antalet grannar till en korrekt delmängd av hörn och storleken på delmängden.
bipartit
En bipartitgraf är en graf vars hörn kan delas upp i två osammanhängande uppsättningar så att hörnen i en uppsättning inte är anslutna till varandra, utan kan anslutas till hörn i den andra uppsättningen. Sagt på ett annat sätt, en tvåpartig graf är en graf utan udda cykler; på motsvarande sätt är det en graf som kan vara korrekt färgad med två färger. Bipartitdiagram skrivs ofta G = ( U , V , E ) där U och V är delmängderna av hörn för varje färg. Men om inte grafen är ansluten kanske den inte har en unik tvåfärgning.
biregulär
Ett dubbelreglerat diagram är ett tvåpartsdiagram där det bara finns två olika hörngrader, en för varje uppsättning av toppunktsdelningen.
blockera
1. Ett block av en graf G är en maximal subgraf som antingen är en isolerad hörnpunkt, en brokant eller en 2-ansluten subgraf. Om ett block är 2-anslutet tillhör varje hörnpar i det en gemensam cykel. Varje kant i en graf hör hemma i exakt ett block.
2. Blockdiagrammet för en graf G är en annan graf vars hörn är blocken av G , med en kant som förbinder två hörn när motsvarande block delar en artikulationspunkt; det vill säga, är det skärnings graf av blocken i G . Blockgrafen för valfri graf är en skog .
3. Blocket skuren (eller block S-spets) diagram över en graf G är en tvådelad graf där en partite uppsättning består av de kapade-hörn av G , och den andra har ett vertex för varje block av G . När G är ansluten är dess block-cutpoint-graf ett träd.
4. Ett blockdiagram (kallas även ett klickträd om det är anslutet och ibland felaktigt kallas ett Husimi -träd) är ett diagram vars block är fullständiga grafer. En skog är ett blockdiagram; så i synnerhet är blockdiagrammet för varje graf ett blockdiagram, och varje blockdiagram kan konstrueras som blockdiagram för en graf.
obligation
En minimal cut-set : en uppsättning kanter vars borttagning kopplar bort grafen, för vilken ingen korrekt delmängd har samma egenskap.
bok
1. En bok , en bokgraf eller en triangulär bok är ett komplett trepartsdiagram K 1,1, n ; en samling av n trianglar sammanfogade vid en gemensam kant.
2. En annan typ av diagram, även kallad en bok, eller en fyrkantig bok, är en samling med 4 -cyklar som är sammanfogade vid en delad kant; den kartesiska produkten av en stjärna med en kant.
3. En inbäddning av en bok är en inbäddning av en graf på en topologisk bok, ett utrymme som bildas genom att ansluta en samling halvplan längs en delad linje. Vanligtvis måste inbäddningens hörn vara på linjen, som kallas inbäddningens ryggrad, och inbäddningens kanter måste ligga inom ett enda halvplan, en av sidorna i boken.
björnbär
En bramble är en samling av varandra berörda anslutna subgrafer, där två subgrafer berör om de delar en toppunkt eller var och en innehåller en slutpunkt på en kant. Ordningen för en bramble är den minsta storleken på en uppsättning hörn som har en icke -ledig skärningspunkt med alla undergrafer. Trebredden på en graf är den maximala ordningen för någon av dess brambles.
gren-sönderdelning
En gren-nedbrytning av G är en hierarkisk klustring av kanterna hos G , som representeras av en orotad binärt träd med dess blad märkta av kanterna på G . Bredden på en gren-sönderdelning är det maximala, över kanterna e på detta binära träd, för antalet delade hörn mellan delgraferna som bestäms av kanterna på G i de två subträden separerade med e . Den branchwidth av G är bredden på någon gren-sönderdelning av minst G .
grenbredd
Se gren-sönderdelning .
bro
1. En bro , ismus eller skärkant är en kant vars borttagning skulle koppla bort grafen. En brygglös graf är en som inte har några broar; ekvivalent, en 2-kant-ansluten graf.
2. Speciellt i samband med planaritetstestning är en cykelbro en maximal subgraf som är oskarp från cykeln och där var och en av kanterna tillhör en väg som är internt avskild från cykeln. Ett ackord är en bro med en kant. En perifer cykel är en cykel med högst en bro; det måste vara ett ansikte i varje plan inbäddning av grafen.
3. En bro i en cykel kan också betyda en väg som förbinder två hörn av en cykel men är kortare än någon av banorna i cykeln som förbinder samma två hörn. En överbryggad graf är en graf där varje cykel med fyra eller flera hörn har en bro.
broslös
En brygglös graf är en graf som inte har några bryggkanter; det vill säga en 2-kant-ansluten graf .
fjäril
1. Fjärilsgrafen har fem hörn och sex kanter; den bildas av två trianglar som delar en toppunkt.
2. Fjärilsnätverket är ett diagram som används som en nätverksarkitektur i distribuerad databehandling, nära besläktat med de kubkopplade cyklerna .

C

C
C n är en n -vertex cyklisk graf ; se cykel .
kaktus
En kaktus graf , kaktus träd, kaktus, eller Husimi träd är en ansluten diagram, i vilket varje kant hör till som mest en cykel. Dess block är cykler eller enstaka kanter. Om dessutom varje hörn hör till högst två block, kallas det en julkaktus.
bur
En bur är en vanlig graf med minsta möjliga ordning för dess omkrets.
kanonisk
kanonisering
En kanonisk form av en graf är en invariant så att två grafer har lika invarianter om och bara om de är isomorfa. Kanoniska former kan också kallas kanoniska invarianter eller fullständiga invarianter, och definieras ibland endast för graferna inom en viss graffamilj. Grafkanonisering är processen för att beräkna en kanonisk form.
kort
En graf bildad från en given graf genom att radera en toppunkt, särskilt i samband med rekonstruktionstanken . Se även kortlek , flersatsen för alla kort i en graf.
ristningsbredd
Skärbredd är en föreställning om grafbredd analog till grenbredd, men med hierarkiska kluster av hörn istället för hierarkiska kluster av kanter.
larv
Ett larvträd eller larv är ett träd där de inre noder inducerar en väg.
Centrum
Den centrala för en graf är uppsättningen av hörn med minimal excentricitet .
kedja
1. Synonym för promenad .
2. Vid tillämpning av metoder från algebraisk topologi till grafer, ett element i ett kedjekomplex , nämligen en uppsättning hörn eller en uppsättning kanter.
Cheeger konstant
Se expansion .
körsbär
En körsbär är en väg på tre hörn.
χ
χ ( G ) (med den grekiska bokstaven chi) är det kromatiska talet för G och χ  ′ ( G ) är dess kromatiska index; se kromatisk och färgning .
barn
I ett rotat träd är ett barn i en toppunkt v en granne till v längs en utgående kant, ett som riktas bort från roten.
ackord
ackord
1. Ett ackord av en cykel är en kant som inte tillhör cykeln, för vilken båda slutpunkterna tillhör cykeln.
2. Ett ackorddiagram är ett diagram där varje cykel med fyra eller flera hörn har ett ackord, så de enda inducerade cyklerna är trianglar.
3. Ett starkt ackorddiagram är ett ackorddiagram där varje cykel med längd sex eller fler har ett udda ackord.
4. En ackordbipartitgraf är inte ackordal (om det inte är en skog); det är en tvåpartig graf där varje cykel med sex eller fler hörn har ett ackord, så de enda inducerade cyklerna är 4-cykler.
5. Ett ackord av en cirkel är ett linjesegment som förbinder två punkter på cirkeln; den skärnings graf av en samling av ackord kallas en cirkel graf .
kromatisk
Har att göra med färgning; se färg . Kromatisk grafteori är teorin om graffärgning. Den kromatiska antal χ ( G ) är det minsta antalet färger som behövs i en korrekt färgning av G . χ  '( G ) är den kromatiska index av G , det minsta antalet färger som behövs i en lämplig kant färgning av G .
valbart
valbarhet
En graf kan k -väljas om den har en listfärgning när varje toppunkt har en lista med k tillgängliga färger. Valbarheten för grafen är den minsta k för vilken den är k -valbar.
cirkel
Ett cirkeldiagram är snittdiagrammet för ackord i en cirkel.
krets
En krets kan referera till ett stängt spår eller ett element i cykelutrymmet (en Eulerian -spänningsundersökning). Den krets rang av ett diagram är dimensionen av sin cykel utrymme.
omkrets
Den omkrets av ett diagram är längden på dess längsta enkel cykel. Diagrammet är Hamiltonian om och endast om dess omkrets är lika med dess ordning.
klass
1. En klass av grafer eller familjer av grafer är en (vanligtvis oändlig) samling av grafer, ofta definierade som graferna som har någon specifik egenskap. Ordet "klass" används snarare än "uppsättning" eftersom, om inte särskilda begränsningar görs (t.ex. att begränsa hörnen som ska dras från en viss uppsättning och definiera kanterna som uppsättningar med två hörn), är klasser av grafer vanligtvis inte uppsättningar när den formaliseras med hjälp av uppsättningsteori.
2. En färgklass för en färgad graf är uppsättningen hörn eller kanter som har en viss färg.
3. I sammanhanget med Vizinges sats , på kantfärgning av enkla grafer, sägs en graf vara av klass ett om dess kromatiska index är lika med sin maximala grad, och klass två om dess kromatiska index är lika med ett plus graden. Enligt Vizinges sats är alla enkla grafer antingen i klass ett eller klass två.
klo
En klo är ett träd med en inre toppunkt och tre löv, eller motsvarande den fullständiga bipartitdiagrammet K 1,3 . En klofri graf är en graf som inte har en inducerad subgraf som är en klo.
klick
En klick är en uppsättning av varandra intilliggande hörn (eller hela subgrafen inducerad av den uppsättningen). Ibland definieras en klick som en maximal uppsättning av varandra intilliggande hörn (eller maximal komplett subgraf), en som inte är en del av någon större sådan uppsättning (eller subgraf). En k -klick är en klick av ordning k . Den klick nummer κ ( G ) av en graf G är ordningen för dess största klick. Ett klickdiagram är ett snittdiagram med maximala klickningar. Se även biclique , en komplett bipartit subgraf.
klick träd
En synonym för ett blockdiagram .
klickbredd
Den klick-bredd av en graf G är det lägsta antalet distinkta etiketter som behövs för att konstruera G genom operationer som skapar en märkt vertex, bildar den disjunkta unionen av två märkta grafer, lägga en kant som förbinder alla par av hörn med givna etiketter eller märka om alla hörn med en given etikett. Diagrammen med klickbredd högst 2 är exakt cographs .
stängd
1. Ett slutet grannskap är ett område som inkluderar dess centrala toppunkt; se grannskap .
2. En stängd promenad är en som börjar och slutar vid samma hörn; se promenad .
3. En graf stängs tillfälligt om den motsvarar sin egen transitiva stängning; se transitiv .
4. En grafegenskap stängs under någon operation på grafer om resultatet när argumentet eller argumenten till operationen har egenskapen. Till exempel stängs ärftliga egenskaper under inducerade subgrafer; monotona egenskaper stängs under subgrafer; och mindre stängda fastigheter stängs under minderåriga.
stängning
1. För transitiv stängning av ett riktat diagram, se transitiv .
2. En förslutning av ett riktat diagram är en uppsättning hörn som inte har några utgående kanter till hörn utanför tillslutningen. Till exempel är en diskbänk en en-vertex stängning. Det stängning problem är problemet med att hitta en nedläggning av lägsta eller högsta vikt.
med-
Detta prefix har olika betydelser som vanligtvis innefattar komplementgrafer . Till exempel är en cograph en graf som produceras av operationer som inkluderar komplementation; en cocoloring är en färgning där varje hörn inducerar antingen en oberoende uppsättning (som vid korrekt färgning) eller en klick (som i en färgning av komplementet).
Färg
färg
1. En graffärgning är en märkning av hörn i en graf med element från en given uppsättning färger, eller motsvarande en uppdelning av hörnen i delmängder, kallade "färgklasser", som var och en är associerad med en av färgerna.
2. Vissa författare använder "färgning", utan kvalifikation, för att betyda en korrekt färgning, en som tilldelar olika färger till slutpunkterna för varje kant. I graffärgning är målet att hitta en korrekt färgning som använder så få färger som möjligt; till exempel bipartite grafer är de grafer som har färgningar med bara två färger, och de fyra färgsatsen säger att varje plan graf kan färgas med högst fyra färger. En graf sägs vara k -färgad om den har (korrekt) färgats med k -färger, och k -färgbar eller k -kromatisk om detta är möjligt.
3. Många färgvariationer har studerats, inklusive kantfärgning (färgningskanter så att inga två kanter med samma slutpunkt delar färg), listfärgning (korrekt färgning med varje hörn begränsad till en delmängd av tillgängliga färger), acyklisk färgning (varje tvåfärgad undergraf är acyklisk), samfärgning (varje färgklass inducerar en oberoende uppsättning eller en klick), fullständig färgning (varannan färgklass delar en kant) och totalfärgning (både kanter och hörn är färgade).
4. Färgnumret på en graf är ett plus degenerationen . Det är så kallat för att tillämpa en girig färgningsalgoritm på en degenerationsordning av grafen använder högst så många färger.
jämförbarhet
En oriktad graf är en jämförbarhetsgraf om dess hörn är elementen i en delvis ordnad uppsättning och två hörn är närliggande när de är jämförbara i delordningen. På motsvarande sätt är en jämförbarhetsgraf en graf som har en transitiv orientering. Många andra klasser av grafer kan definieras som jämförbarhetsgrafer för speciella typer av delordningar.
komplement
Den komplementgraf av en enkel graf G är en annan graf på samma vertex uppsättning som G , med en kant för varje två hörn som inte är angränsande i G .
komplett
1. En komplett graf är en där varannan hörn ligger intill: alla kanter som kan finnas finns. En komplett graf med n hörn betecknas ofta K n . En fullständig tvåpartig graf är en där varannan hörn på motsatta sidor av partitionen av hörn ligger intill varandra. En komplett bipartit graf med ett hörn på den ena sidan av skilje och b hörn på den andra sidan är ofta betecknas K a , b . Samma terminologi och notation har också utökats för att slutföra flerpartsdiagram , grafer där hörnen är indelade i mer än två delmängder och varje par hörn i olika delmängder ligger intill varandra; om antalet hörn i delmängd är en , b , c , ... då denna graf betecknas K a , b , c , ... .
2. Ett slutförande av en given graf är en supergraf som har någon önskad egenskap. Till exempel är en ackordfärdigställande en supergraf som är en ackordgraf.
3. En komplett matchning är en synonym för en perfekt matchning ; se matchning .
4. En fullständig färgning är en korrekt färgning där varje par av färger används för slutpunkterna på minst en kant. Varje färgning med ett minsta antal färger är komplett, men det kan finnas fullständiga färgningar med större antal färger. Det akromatiska antalet i en graf är det maximala antalet färger i en komplett färgning.
5. En fullständig invariant av en graf är en synonym för en kanonisk form, en invariant som har olika värden för icke-isomorfa grafer.
komponent
En ansluten komponent i en graf är en maximalt ansluten subgraf. Termen används också för maximala undergrafer eller delmängder av en grafs hörn som har en högre anslutningsordning, inklusive bikopplade komponenter , trikopplade komponenter och starkt anslutna komponenter .
kondensation
Den kondensation av en riktad graf G är en riktad acyklisk graf med ett vertex för varje starkt kopplad komponent i G , och en kant som förbinder paren av komponenter som innehåller de två ändpunkterna av åtminstone en kant i G .
kon
En graf som innehåller en universell toppunkt .
ansluta
Orsak att vara ansluten .
ansluten
En ansluten graf är en där varje par hörnpar utgör slutpunkterna för en väg. Högre former av anslutning inkluderar stark anslutning i riktade grafer (för varje två hörn finns det vägar från en till den andra i båda riktningarna), k -vertex -anslutna grafer (att ta bort färre än k -hörn kan inte koppla bort grafen) och k -kant -kopplade grafer (att ta bort färre än k -kanter kan inte koppla bort grafen).
samtala
Det omvända diagrammet är en synonym för transponeringsdiagrammet; se transponering .
kärna
1. En k -poäng är den inducerade subgrafen som bildas genom att ta bort alla hörn med grad mindre än k , och alla hörn vars grad blir mindre än k efter tidigare borttagningar. Se degeneration .
2. En kärna är en graf G så att varje grafhomomorfism från G till sig själv är en isomorfism.
3. Kärnan i en graf G är en minimal graf H så att det finns homomorfismer från G till H och vice versa. H är unikt för isomorfism. Det kan representeras som en inducerad delgraf av G och är en kärna i den meningen att alla dess självhomomorfismer är isomorfismer.
4. I teorin om grafmatchningar är kärnan i en graf en aspekt av dess sönderdelning av Dulmage – Mendelsohn , bildad som föreningen av alla maximala matchningar.
cotree
1. Komplementet till ett spännande träd .
2. En rotad trädstruktur som används för att beskriva en cograph , där varje cograph toppunkt är ett blad av trädet, varje intern nod av trädet är märkt med 0 eller 1, och två cograph vertices är intilliggande om och bara om deras lägsta gemensamma förfader i trädet är märkt 1.
omslag
Ett vertex -lock är en uppsättning hörn som faller mot varje kant i ett diagram. Ett kantskydd är en uppsättning kanter som faller in på varje toppunkt i ett diagram. En uppsättning subgrafer av en graf täcker den grafen om dess förening- tagen topp-vis och kant-vis-är lika med grafen.
kritisk
En kritisk graf för en given egenskap är en graf som har egenskapen men så att varje undergraf som bildas genom att ta bort en enda toppunkt inte har egenskapen. Till exempel är en faktorkritisk graf en som har en perfekt matchning (en 1-faktor) för varje raderingspunkt, men (eftersom den har ett udda antal hörn) har ingen perfekt matchning i sig. Jämför hypo- , används för grafer som inte har någon egenskap men som varje radering med en vertex gör.
kub
kubisk
1.   Kubgraf , åtta-toppunktsdiagrammet för hörnen och kanterna på en kub.
2.   Hyperkubgraf , en högre dimensionell generalisering av kubdiagrammet.
3.   Vikt kubgraf , bildad av en hyperkub genom att lägga till en matchande anslutning motsatta hörn.
4.   Halverad kubgraf , halva kvadraten i en hyperkubdiagram.
5.   Delvis kub , en avståndsbevarande delgraf av en hyperkub.
6. Kuben i en graf G är grafeffekten G 3 .
7.   Kubikgraf , ett annat namn för en 3 -regelbunden graf, en där varje hörn har tre infallande kanter.
8.   Kubkopplade cykler , en kubikgraf som bildas genom att varje toppunkt i en hyperkub ersätts med en cykel.
skära
cut-set
Ett snitt är en delning av hörn i en graf i två delmängder, eller uppsättningen (även känd som en snittuppsättning) av kanter som sträcker sig över en sådan partition, om den uppsättningen inte är tom. Det sägs att en kant spänner över partitionen om den har slutpunkter i båda delmängderna. Således avlägsnar borttagningen av en skärsats från en ansluten graf den.
skärpunkt
Se artikulationspunkten .
klippa utrymme
Den skurna utrymme av en kurva är en GF (2) - vektorrum med cut-uppsättning s av grafen som sina element och symmetrisk skillnad uppsättningar som dess vektoradditionsoperationen.
cykel
En cykel kan antingen hänvisa till en stängd promenad (även kallad en rundtur ) eller mer specifikt till en stängd promenad utan upprepade hörn och följaktligen kanter (även kallad en enkel cykel). I båda fallen anses valet av första toppunkt vanligtvis vara oviktigt: cykliska permutationer av promenaden ger samma cykel. Viktiga specialfall av cykler inkluderar Hamiltonian cykler , inducerade cykler , perifera cykler och den kortaste cykeln, som definierar omkretsen av en graf. En k -cykel är en cykel med längden k ; till exempel är en 2 -cykel en digon och en 3 -cykel är en triangel. En cykeldiagram är en graf som i sig är en enkel cykel; en cykeldiagram med n hörn betecknas vanligen C n . Den cykel utrymmet är ett vektorrum genereras av enkla cykler i en graf.

D

DAG
Förkortning för riktad acyklisk graf , en riktad graf utan några riktade cykler.
däck
Multisatsen av grafer som bildas från en enda graf G genom att radera en enda toppunkt på alla möjliga sätt, särskilt i samband med rekonstruktionstanken . Ett kantdäck bildas på samma sätt genom att radera en enda kant på alla möjliga sätt. Graferna i en kortlek kallas också kort . Se även kritiska (grafer som har en egenskap som inte innehas av något kort) och hypo- (grafer som inte har en egenskap som innehas av alla kort).
sönderfall
Se trädets sönderdelning , sökvägsnedbrytning eller grennedbrytning .
degenererad
degeneration
En k -genererad graf är en oriktad graf där varje inducerad subgraf har minsta grad högst k . Den degenerering av ett diagram är den minsta k för vilka det är k -degenerate. En degenerationsordning är en ordning av hörnen så att varje hörn har minsta grad i den inducerade subgrafen av den och alla senare hörn; i en degenerationsordning av en k -genererad graf har varje hörn högst k senare grannar. Degeneration är också känt som k -core -nummer, bredd och koppling, och ett plus degenerationen kallas också färgnummer eller Szekeres – Wilf -nummer. k -genererade grafer har också kallats k -induktiva grafer.
grad
1. Graden av en toppunkt i en graf är dess antal infallande kanter. Graden för en graf G (eller dess maximala grad) är maximalt för graderna på dess hörn, ofta betecknade Δ ( G ) ; lägsta grad av G är minimiet av dess toppunktsgrader, ofta betecknade δ ( G ) . Grad kallas ibland valens ; graden av v i G kan betecknas d G ( v ) , d ( G ) eller deg ( v ) . Den totala graden är summan av graderna för alla hörn; med handskakande lemma är det ett jämnt tal. Den grad sekvensen är insamling av grader i alla hörn i sorterad ordning från största till minsta. I en riktad graf kan man skilja mellan grad (antal inkommande kanter) och utgradering (antal utgående kanter).
2. Homomorfismgraden för en graf är en synonym för dess Hadwiger -nummer , storleksordningen för den största klickminor.
A, δ
Δ ( G ) (med den grekiska bokstaven delta) är den maximala graden av en toppunkt i G , och δ ( G ) är lägsta graden; se examen .
densitet
I en graf över n -noder är densiteten förhållandet mellan antalet kanter på grafen och antalet kanter i en komplett graf på n -noder. Se tät graf .
djup
Djupet på en nod i ett rotat träd är antalet kanter i sökvägen från roten till noden. Till exempel är rotens djup 0 och djupet för någon av dess intilliggande noder är 1. Det är nivån för en nod minus en. Observera dock att vissa författare istället använder djup som en synonym för nivån på en nod.
diameter
Diametern på en ansluten graf är den längsta längden på en kortaste väg . Det vill säga det är maximalt för avstånden mellan hörnpar i grafen. Om grafen har vikter på sina kanter mäter dess vägda diameter banlängden med summan av kantvikterna längs en bana, medan den oviktade diametern mäter banlängden med antalet kanter. För frånkopplade grafer varierar definitionerna: diametern kan definieras som oändlig, eller som den största diametern för en ansluten komponent, eller den kan vara odefinierad.
diamant-
Den diamantgraf är en oriktad graf med fyra hörn och fem kanter.
ansluten
Stark ly ansluten . (Får inte förväxlas med bortkopplad )
digon
En digon är en enkel cykel med längd två i ett riktat diagram eller en multigraf. Digoner kan inte förekomma i enkla oriktade grafer eftersom de kräver att samma kant upprepas två gånger, vilket bryter mot definitionen av enkel .
digraph
Synonym för riktad graf .
dipat
Se riktad väg .
direkt föregångare
Svansen på en riktad kant vars huvud är det givna hörnet.
direkt efterträdare
Huvudet på en riktad kant vars svans är det givna hörnet.
riktad
En riktad graf är en i vilken kanterna har en särskild riktning, från en toppunkt till en annan. I en blandad graf är en riktad kant återigen en som har en särskild riktning; riktade kanter kan också kallas bågar eller pilar.
riktad båge
Se pil .
riktad kant
Se pil .
riktad linje
Se pil .
riktad väg
En bana där alla kant s har samma riktning . Om en riktad väg leder från toppunkt x till toppunkt y , är x en föregångare till y , y är en efterföljare av x och y sägs nås från x .
riktning
1. Det asymmetriska förhållandet mellan två intilliggande hörn i en graf , representerat som en pil .
2. Det asymmetriska förhållandet mellan två hörn i en riktad väg .
koppla ifrån
Orsak att kopplas bort .
osammanhängande
Inte ansluten .
osammanhängande
1. Två subgrafer är kantdelade om de inte delar några kanter, och vertex disjoint om de inte delar några hörn.
2. Den osammanhängande föreningen mellan två eller flera grafer är en graf vars toppunkt och kantuppsättningar är de sammanfogade föreningarna i motsvarande uppsättningar.
distans
Den avståndet mellan vilka som helst två hörn i en graf är längden på den kortaste vägen som har de två hörn som sina ändpunkter.
domatisk
En domatisk partition av en graf är en delning av hörnen i dominerande uppsättningar. Den Domatic antal av grafen är det maximala antalet dominerande uppsättningar i en sådan partition.
dominerande
En dominerande uppsättning är en uppsättning hörn som inkluderar eller ligger intill varje hörn i grafen; inte att förväxla med en toppunktskydd, en toppunktsuppsättning som faller mot alla kanter i grafen. Viktiga specialtyper av dominerande uppsättningar inkluderar oberoende dominerande uppsättningar (dominerande uppsättningar som också är oberoende uppsättningar) och anslutna dominerande uppsättningar (dominerande uppsättningar som framkallade anslutna subgrafer). En enda vertex-dominerande uppsättning kan också kallas en universell toppunkt. Domineringsnumret för en graf är antalet hörn i den minsta dominerande uppsättningen.

E

E
E ( G ) är kantuppsättningen av G ; se kantinställning .
öra
Ett öra i en graf är en väg vars slutpunkter kan sammanfalla men där det annars inte finns några repetitioner av hörn eller kanter.
nedbrytning av örat
En öronsönderdelning är en uppdelning av kanterna på en graf i en sekvens av öron, var och en av deras slutpunkter (efter det första) tillhör ett tidigare öra och var och en av vars inre punkter inte tillhör något tidigare öra. Ett öppet öra är en enkel väg (ett öra utan upprepade hörn), och ett öppet öra är sönderdelning där varje öra efter det första är öppet; en graf har ett öppet öra sönderdelning om och bara om den är ansluten. Ett öra är udda om det har ett udda antal kanter, och ett udda öra sönderdelning är ett öra sönderdelning där varje öra är udda; en graf har en udda öra sönderdelning om och bara om den är faktor-kritisk.
excentricitet
Excentriciteten hos en vertex är det längsta avståndet från den till någon annan vertex.
kant
En kant är (tillsammans med hörn) en av de två grundenheterna ur vilka grafer är konstruerade. Varje kant har två (eller i hypergrafer, fler) hörn som den är fäst till, kallad dess slutpunkter. Kanter kan vara riktade eller oriktade; oriktade kanter kallas också linjer och riktade kanter kallas också bågar eller pilar. I en oriktad enkel graf kan en kant representeras som uppsättningen av dess hörn, och i en riktad enkel graf kan den representeras som ett ordnat par av dess hörn. En kant som förbinder hörn x och y skrivs ibland xy .
kantskärning
En uppsättning av kant s vars avlägsnande kopplar den grafen . Ett snitt med en kant kallas en bro , ismus eller skärkant .
kantuppsättning
Uppsättningen av kanter för en given graf G , ibland betecknad med E ( G ) .
kantlös graf
Den kantlösa grafen eller helt frånkopplad graf på en given uppsättning hörn är den graf som inte har några kanter. Det kallas ibland det tomma diagrammet, men denna term kan också referera till en graf utan hörn.
inbäddning
En inbäddning av en graf är en topologisk representation av en graf som en delmängd av ett topologiskt utrymme där varje hörn representeras som en punkt, varje kant representerad som en kurva med kantens slutpunkter som kurvornas slutpunkter, och inga andra skärningspunkter mellan hörn eller kanter. Ett plant diagram är en graf som har en sådan inbäddning i det euklidiska planet, och en toroidal graf är en graf som har en sådan inbäddning i en torus. De genus av ett diagram är de minsta möjliga släktet av en tvådimensionell grenrör på vilken den kan vara inbäddad.
tom graf
1. Ett kantlöst diagram på en uppsättning hörnfria.
2. Ordningen-noll-grafen , en graf utan hörn och inga kanter.
slutet
Ett slut på en oändlig graf är en ekvivalensklass av strålar, där två strålar är ekvivalenta om det finns en tredje stråle som innehåller oändligt många hörn från dem båda.
slutpunkt
En av de två hörnen förenade med en given kant, eller en av de första eller sista hörnpunkterna på en promenad, spår eller stig. Den första slutpunkten för en given riktad kant kallas svansen och den andra slutpunkten kallas huvudet .
uppräkning
Grafuppräkning är problemet med att räkna graferna i en given grafklass, som en funktion av deras ordning. Mer allmänt kan uppräkningsproblem hänvisa antingen till problem med att räkna en viss klass av kombinatoriska objekt (såsom klickningar, oberoende uppsättningar, färgningar eller spänningsträd), eller att algoritmiskt lista alla sådana objekt.
Eulerian
En Eulerian -väg är en promenad som använder varje kant i ett diagram exakt en gång. En Eulerian -krets (även kallad en Eulerian -cykel eller en Euler -rundtur) är en stängd promenad som använder varje kant exakt en gång. En Eulerian graf är en graf som har en Eulerian krets. För en oriktad graf betyder detta att grafen är ansluten och varje toppunkt har jämn grad. För en riktad graf betyder detta att grafen är starkt sammankopplad och varje toppunkt har grad lika med utgraden. I vissa fall lossas anslutningskravet och en graf som endast uppfyller examenskraven kallas Eulerian.
även
Delbart med två; till exempel är en jämn cykel en cykel vars längd är jämn.
expander
En expandergraf är en graf vars kantexpansion, toppunktsexpansion eller spektral expansion exponeras från noll.
expansion
1. expansions kanten, isoperimetriska nummer eller Cheeger konstant av en graf G är minimiförhållandet, över underuppsättningar S av högst halv av hörnen i G , av antalet kanter som lämnar S till antalet hörn i S .
2. Spetsens expansion, vertex isoperimetriska tal eller förstoringen av en graf G är minimikvoten, över delmängder S på högst hälften av G -hörnen , av antalet hörn utanför men intill S till antalet hörn i S .
3. Den unika granne expansion av en graf G är minimiförhållandet, över undergrupper av högst hälften av det hörn av G , av antalet hörn utanför S men i anslutning till en unik vertex i S till antalet hörn i S .
4. Den spektrala expansionen av en d -regelbunden graf G är spektralgapet mellan det största egenvärdet d i dess adjacensmatris och det näst största egenvärdet.
5. En familj av grafer har begränsat expansionen om alla dess r -granna minderåriga har ett förhållande mellan kanter och hörn som begränsas av en funktion av r och polynomutvidgning om funktionen av r är ett polynom.

F

ansikte
I en plan graf eller inbäddning av en graf , en ansluten komponent i delmängden av planet eller ytan på inbäddningen som är oskarp från grafen. För en inbäddning i planet kommer alla utom ett ansikte att begränsas; det enda exceptionella ansiktet som sträcker sig till oändligheten kallas ytterytan.
faktor
En faktor i en graf är en spännande undergraf: en undergraf som inkluderar alla hörn i grafen. Termen används främst i samband med vanliga subgrafer: en k -faktor är en faktor som är k -regelbunden. Framför allt är en 1 -faktor samma sak som en perfekt matchning. En faktorkritisk graf är en graf för vilken radering av ett hörn ger en graf med en 1 -faktor.
faktorisering
En graffaktorisering är en uppdelning av grafens kanter i faktorer; en k -faktorisering är en uppdelning i k -faktorer. Exempelvis en 1 -factorization är en kant färg med den ytterligare egenskapen att varje vertex infaller till en kant av varje färg.
familj
En synonym för klass .
ändlig
En graf är ändlig om den har ett begränsat antal hörn och ett begränsat antal kanter. Många källor antar att alla grafer är ändliga utan att uttryckligen säga det. En graf är lokalt slutlig om varje toppunkt har ett begränsat antal infallande kanter. En oändlig graf är en graf som inte är ändlig: den har oändligt många hörn, oändligt många kanter eller båda.
första beställning
Den första ordningens logik för grafer är en form av logik där variabler representerar hörn i en graf, och det finns ett binärt predikat för att testa om två hörn är intill varandra. Att skilja från andra ordningens logik, där variabler också kan representera uppsättningar hörn eller kanter.
-flaxa
För en uppsättning av vertex X , ett X är -flap en ansluten komponent av den inducerade subgraf bildad genom att ta bort X . Flikterminologin används vanligtvis i samband med tillflyktsorter , funktioner som kartlägger små uppsättningar hörn till deras flikar. Se även cykelns bro , som antingen är en flik på cykelhörnen eller ett ackord av cykeln.
förbjuden
En förbjuden grafkarakterisering är en karakterisering av en familj av grafer som de grafer som inte har vissa andra grafer som subgrafer, inducerade subgrafer eller minderåriga. Om H är en av graferna som inte förekommer som en subgraf, inducerad subgraf eller mindre, sägs H vara förbjudet.
skog
En skog är en oriktad graf utan cykler (en oenig förening av orotade träd), eller en riktad graf som bildas som en oskarv förening av rotade träd.
Frucht
1.   Robert Frucht
2. Frucht -grafen , en av de två minsta kubikgraferna utan otrevliga symmetrier.
3.   Frucht teorem att varje ändlig grupp är gruppen av symmetrier i en ändlig graf.
full
Synonym för inducerad .
funktionell graf
En funktionell graf är en riktad graf där varje hörn har en övergraderad. På motsvarande sätt är en funktionell graf en maximalt riktad pseudoforest.

G

G
En variabel som ofta används för att markera en graf.
släkte
Släktet för en graf är det minsta släktet för en yta på vilken det kan bäddas in; se inbäddning .
geodetisk
Som substantiv är en geodesik en synonym för en kortaste väg . När det används som adjektiv betyder det relaterat till kortaste vägar eller kortaste vägavstånd.
jätte
I teorin om slumpmässiga grafer är en jättekomponent en ansluten komponent som innehåller en konstant bråkdel av grafens hörn. I standardmodeller av slumpmässiga grafer finns det vanligtvis högst en jättekomponent.
omkrets
Den omkrets av ett diagram är längden av dess kortaste cykeln.
Graf
Det grundläggande föremålet för studien i grafteori, ett system med hörn som är parvis förbundna med kanter. Ofta uppdelat i riktade grafer eller oriktade grafer beroende på om kanterna har en orientering eller inte. Blandade grafer inkluderar båda typerna av kanter.
girig
Producerad av en girig algoritm . Till exempel är en girig färgning av en graf en färgning som produceras genom att betrakta hörnen i någon sekvens och tilldela varje toppunkt den första tillgängliga färgen.
Grötzsch
1.   Herbert Grötzsch
2. Grötzsch-grafen , den minsta triangelfria grafen som kräver fyra färger i rätt färg.
3.   Grötzsch teorem om att triangelfria plana grafer alltid kan färgas med högst tre färger.
Grundy -nummer
1. Grundy-talet i en graf är det maximala antalet färger som produceras av en girig färgning , med en dåligt vald toppunktsordning.

H

H
En variabel som används ofta för att beteckna en graf, speciellt när en annan graf redan har betecknats med G .
H -färgning
En H -coloring av en graf G (där H är också ett diagram) är en homomorfism från H till G .
H -fritt
En graf är H -fri om den inte har en inducerad subgraf isomorf för H , det vill säga om H är en förbjuden inducerad subgraf. De H -fria diagram är familjen av alla grafer (eller, ofta, alla ändliga grafer) som är H -fri. Till exempel är de triangelfria graferna de grafer som inte har en triangelgraf som subgraf. Egenskapen att vara H -fri är alltid ärftlig. En graf är H -minor fri om den inte har en mindre isomorphic till H .
Hadwiger
1.   Hugo Hadwiger
2. Hadwiger -numret på en graf är storleksordningen för den största kompletta minor i grafen. Det kallas också sammandragningsklicknummer eller homomorfismgraden.
3. Hadwiger -gissningen är gissningen att Hadwiger -talet aldrig är mindre än det kromatiska talet.
Hamiltonian
En Hamiltonian -väg eller Hamiltonian -cykel är en enkel spännväg eller enkel spänningscykel: den täcker alla hörn i grafen exakt en gång. En graf är Hamiltonian om den innehåller en Hamiltonian -cykel och spårbar om den innehåller en Hamiltonian -väg.
hamn
En k - haven är en funktion som kartlägger varje uppsättning X med färre än k hörn till en av dess flikar, vilket ofta uppfyller ytterligare konsistensvillkor. Orden för en fristad är talet k . Havens kan användas för att karakterisera trädbredden på ändliga grafer och ändarna och Hadwiger -antalet oändliga grafer.
höjd
1. Höjden på en nod i ett rotat träd är antalet kanter i en maximal väg, som går bort från roten (dvs dess noder har strikt ökande djup), som börjar vid den noden och slutar vid ett blad.
2. Höjden på ett rotat träd är höjden på dess rot. Det vill säga höjden på ett träd är antalet kanter på en längsta möjliga väg, som går bort från roten, som börjar vid roten och slutar vid ett blad.
3. Höjden på en riktad acyklisk graf är den maximala längden för en riktad väg i denna graf.
ärftlig
En ärftlig egenskap av grafer är en egenskap som är stängd under inducerade subgrafer: om G har en ärftlig egendom, då så måste varje inducerad subgraf av G . Jämför monoton (stängd under alla subgrafer) eller minor-closed (stängd under minderåriga).
sexhörning
En enkel cykel som består av exakt sex kanter och sex hörn.
hål
Ett hål är en inducerad cykel med längd fyra eller mer. Ett udda hål är ett hål med udda längd. Ett anti-hål är en inducerad subgraf av ordning fyra vars komplement är en cykel; på motsvarande sätt är det ett hål i komplementgrafen. Denna terminologi används huvudsakligen i samband med perfekta grafer, som kännetecknas av den starka perfekta grafsatsen som graferna utan udda hål eller udda antihål. De hålfria graferna är desamma som ackordgraferna .
homomorfisk ekvivalens
Två grafer är homomorfiskt ekvivalenta om det finns två homomorfismer, en från varje graf till den andra grafen.
homomorfism
1. En grafhomomorfism är en kartläggning från hörnuppsättningen för en graf till hörnuppsättningen för en annan graf som kartlägger intilliggande hörn till intilliggande hörn. Denna typ av kartläggning mellan grafer är den som är vanligast vid kategoriteoretiska metoder för grafteori. En korrekt graffärgning kan likvärdigt beskrivas som en homomorfism till en komplett graf.
2. Homomorfismgraden för en graf är en synonym för dess Hadwiger -nummer , storleksordningen för den största klickminor.
hyperkant
En kant i en hypergraf , med valfritt antal slutpunkter, i motsats till kravet att grafernas kanter har exakt två slutpunkter.
hyperkub
En hyperkubgraf är en graf som bildas från hörn och kanter på en geometrisk hyperkub .
hypergraf
En hypergraf är en generalisering av en graf där varje kant (kallad en hyperkant i detta sammanhang) kan ha mer än två slutpunkter.
hypo-
Detta prefix, i kombination med en grafegenskap, indikerar en graf som inte har egenskapen men så att varje subgraf som bildas genom att ta bort en enda toppunkt har egenskapen. Till exempel är en hypohamiltonian graf en som inte har en Hamiltonian cykel, men för vilken varje radering med en toppunkt producerar en Hamiltonian subgraf. Jämför kritiska , används för grafer som har en egenskap men som varje radering med en vertex inte gör.

I

i examen
Antalet inkommande kanter i en riktad graf; se examen .
frekvens
En förekomst i en graf är ett vertex-edge-par så att toppunkten är en slutpunkt för kanten.
incidensmatris
Den infalls matris av ett diagram är en matris vars rader är indexerade genom hörn i grafen och vars kolumner är indexerade av kanter, med en en i cellen för rad i och kolumn j när vertex i och kant j infaller, och en noll annars.
incident
Förhållandet mellan en kant och en av dess slutpunkter.
makalöshet
En oförenlighet graf är komplementet till en jämförbarhet graf ; se jämförbarhet .
självständig
1. En oberoende uppsättning är en uppsättning hörn som inducerar en kantlös subgraf. Det kan också kallas en stabil uppsättning eller en coclique. Den oberoende nummer α ( G ) är storleken av den maximala oberoende uppsättning .
2. I den grafiska matroid för en graf är en delmängd av kanter oberoende om motsvarande undergraf är ett träd eller en skog. I den bicirkulära matroid är en delmängd av kanter oberoende om motsvarande delbild är en pseudoforest .
likgiltighet
En likgiltighetsgraf är ett annat namn för ett korrekt intervalldiagram eller enhetsintervalldiagram; se ordentligt .
inducerad
En inducerad subgraf eller fullständig subgraf av en graf är en subgraf som bildas från en delmängd av hörn och från alla kanter som har båda slutpunkterna i delmängden. Särskilda fall inkluderar inducerade banor och inducerade cykler , inducerade subgrafer som är vägar eller cykler.
induktiv
Synonym för degenererad .
oändlig
En oändlig graf är en som inte är ändlig; se ändligt .
inre
En hörn av en stig eller ett träd är inre om det inte är ett blad; det vill säga om dess grad är större än en. Två vägar är internt skilda (vissa människor kallar det oberoende ) om de inte har någon toppunkt gemensamt, förutom den första och den sista.
genomskärning
1. Skärningspunkten mellan två grafer är deras största vanliga undergraf, grafen som bildas av hörn och kanter som hör till båda graferna.
2. Ett snittdiagram är en graf vars hörn motsvarar uppsättningar eller geometriska objekt, med en kant mellan två hörn exakt när motsvarande två uppsättningar eller objekt har en icke -ledig skärning. Flera klasser av grafer kan definieras som korsningsgraferna för vissa typer av objekt, till exempel ackorddiagram (korsningsgrafer för ett träds träd), cirkeldiagram (korsningsgrafer för ackord i en cirkel), intervallgrafer (intersektionsgrafer för intervall) av en linje), linjediagram (skärningskurvor för kanterna på en graf) och klickdiagram (skärningskurvor för de maximala klickarna i en graf). Varje graf är en skärningslinje för vissa grupper av uppsättningar, och denna familj kallas en skärningspresentation av grafen. Den skärnings antal av en graf G är det lägsta totala antalet element i någon korsning representation av G .
intervall
1. Ett intervalldiagram är ett skärningsschema med intervall på en linje .
2. Intervallet [ u , v ] i en graf är föreningen av alla kortaste vägar från u till v .
3. Intervalltjocklek är en synonym för vägbredd .
invariant
En synonym med egendom .
inverterad pil
En pil med motsatt riktning jämfört med en annan pil. Pilen ( y , x ) är pilens inverterade pil ( x , y ) .
isolerat
En isolerad hörnpunkt i en graf är en hörn vars grad är noll, det vill säga en hörn utan infallande kanter.
isomorf
Två grafer är isomorfa om det finns en isomorfism mellan dem; se isomorfism .
isomorfi
En grafisomorfism är en en-till-en-incidens som bevarar korrespondensen mellan hörnen och kanterna på en graf till hörnen och kanterna på en annan graf. Två grafer relaterade på detta sätt sägs vara isomorfa.
isoperimetrisk
Se expansion .
näs
Synonym för bridge , i betydelsen en kant vars borttagning kopplar bort grafen.

K

K
För notering för fullständiga grafer, kompletta bipartitdiagram och kompletta multipartdiagram, se komplett .
κ
κ ( G ) (med den grekiska bokstaven kappa) är storleksordningen för den maximala klicken i G ; se klick .
kärna
En kärna i en riktad graf är en uppsättning hörn som är både stabil och absorberande .
Knut
En oundviklig sektion av en riktad graf . Se knut (matematik) och knutteori .

L

L
L ( G ) är linjediagrammet för G ; se rad .
märka
1. Information associerad med en toppunkt eller kant på en graf. En märkt graf är en graf vars hörn eller kanter har etiketter. Termerna hörnet-märkta eller kantmärkta kan användas för att ange vilka objekt i en graf som har etiketter. Grafmärkning avser flera olika problem med att tilldela etiketter till grafer som är föremål för vissa begränsningar. Se även graffärgning , där etiketterna tolkas som färger.
2. I samband med grafuppräkning sägs det att hörnen i en graf är märkta om de alla kan skiljas från varandra. Detta kan till exempel göras sant genom att fixa en en-till-en-korrespondens mellan hörnen och heltalen från 1 till grafens ordning. När hörnen är märkta räknas grafer som är isomorfa mot varandra (men med olika toppunktsordningar) som separata objekt. När hörnen däremot är omärkta räknas inte grafer som är isomorfa mot varandra separat.
blad
1. En bladpunkt eller hängande toppunkt (särskilt i ett träd) är en toppunkt vars grad är  1 . En bladkant eller hängande kant är kanten som förbinder ett bladpunkt med sin enda granne.
2. Ett blad effekten av ett träd är ett diagram vars hörn är bladen av trädet och vars kanter connect blad vars avstånd i trädet är som mest en given tröskel.
längd
I en oviktad graf är längden på en cykel, väg eller promenad antalet kanter den använder. I en vägd graf kan det istället vara summan av vikterna på kanterna som den använder. Längd används för att definiera den kortaste vägen , omkretsen (kortaste cykellängden) och den längsta vägen mellan två hörn i en graf.
nivå
1. Detta är djupet hos en nod plus 1, även om vissa definierar det istället för att vara synonym med djup . En nodnivå i ett rotat träd är antalet noder i sökvägen från roten till noden. Till exempel har roten nivå 1 och någon av dess intilliggande noder har nivå 2.
2. En uppsättning av alla noder som har samma nivå eller djup.
linje
En synonym för en oriktad kant. Den linjediagrammet L ( G ) av en graf G är en graf med ett vertex för varje kant av G och en kant för varje par av kanter som delar en slutpunkt i G .
koppling
En synonym för degeneration .
lista
1. En angränsningslista är en datorrepresentation av grafer för användning i grafalgoritmer.
2.   Listfärgning är en variant av graffärgning där varje toppunkt har en lista över tillgängliga färger.
lokal
En lokal egenskap hos en graf är en egenskap som endast bestäms av grannskapen i hörnen i grafen. Till exempel är en graf lokalt ändlig om alla dess grannskap är ändliga.
slinga
En slinga eller självslinga är en kant vars båda ändpunkter är samma hörn. Det bildar en cykel med längd 1 . Dessa är inte tillåtna i enkla grafer.

M

förstoring
Synonym för vertex expansion .
motsvarande
En matchning är en uppsättning kanter där inga två delar någon toppunkt. En toppunkt matchas eller mättas om det är en av slutpunkterna för en kant i matchningen. En perfekt matchning eller komplett matchning är en matchning som matchar varje toppunkt; det kan också kallas en 1-faktor och kan bara existera när ordningen är jämn. En nästan perfekt matchning, i en graf med udda ordning, är en som mättar alla utom en toppunkt. En maximal matchning är en matchning som använder så många kanter som möjligt; matchningsnumret α ′ ( G ) i en graf G är antalet kanter i en maximal matchning. En maximal matchning är en matchning som inga ytterligare kanter kan läggas till.
maximal
1. En subgraf för given graf G är maximal för en viss egenskap om den har den egenskapen men ingen annan supergraf av den som också är en subgraf av G har också samma egenskap. Det vill säga, det är ett maximalt element i subgraferna med egenskapen. Till exempel är en maximal klick en komplett subgraf som inte kan utökas till en större komplett subgraf. Ordet "maximal" bör skiljas från "maximalt": en maximal subgraf är alltid maximal, men inte nödvändigtvis tvärtom.
2. En enkel graf med en given egenskap är maximal för den egenskapen om det inte är möjligt att lägga till fler kanter till den (hålla hörnpunkten oförändrad) samtidigt som både grafens enkelhet och egenskapen bevaras. Således är till exempel ett maximalt plan diagram ett plant diagram så att om du lägger till fler kanter till det skulle det skapa en icke-plan graf.
maximal
En undergraf för en given graf G är maximal för en viss egenskap om den är den största undergrafen (efter ordning eller storlek) bland alla delgrafer med den egenskapen. Till exempel är en maximal klick någon av de största klickarna i en given graf.
median
1. En median för en trippel av hörn, en toppunkt som tillhör de kortaste banorna mellan alla par av hörn, särskilt i mediangrafer och modulgrafer .
2. En mediangraf är en graf där alla tre hörn har en unik median.
Meyniel
1. Henri Meyniel, fransk grafteoretiker.
2. En Meyniel -graf är en graf där varje udda cykel med längd fem eller mer har minst två ackord.
minimal
En subgraf av en given graf är minimal för en viss egenskap om den har den egenskapen men ingen riktig subgraf av den har också samma egenskap. Det vill säga att det är ett minimalt inslag i delgraferna med egenskapen.
minsta snitt
Ett snitt vars skärsats har minsta totalvikt, möjligen begränsad till snitt som skiljer ett särskilt hörnpar; de kännetecknas av maxflödesminskningssatsen .
mindre
En graf H är en mindre av en annan graf G om H kan erhållas genom att ta bort kanter eller hörn från G och sammandragande kanter i G . Det är en grund minor om den kan formas som en minor på ett sådant sätt att de subgrafer av G som dragits ihop för att bilda hörn av H alla har liten diameter. H är en topologisk moll av G om G har en subgraf som är en underavdelning av H . En graf är H -minor -fri om den inte har H som minor. En familj av grafer är mindre stängd om den stängs under minderåriga; den Robertson-Seymour teoremet karakteriserar smärre slutna familjer som har en ändlig uppsättning av förbjudna minderåriga.
blandad
En blandad graf är en graf som kan innehålla både riktade och oriktade kanter.
modul-
1.   Modulär graf , en graf där varje trippel av hörn har minst en median toppunkt som tillhör de kortaste banorna mellan alla par i trippeln.
2.   Modulär sönderdelning , en sönderdelning av en graf till subgrafer inom vilka alla hörn ansluter sig till resten av grafen på samma sätt.
3.   Modularitet för en grafklustering, skillnaden mellan antalet tvärklusterkanter från dess förväntade värde.
monoton
En monoton egenskap av grafer är en egenskap som är stängd i subgrafer: om G har en ärftlig egendom, då så måste varje subgraph av G . Jämför ärftliga (stängda under inducerade subgrafer) eller minor-closed (stängda under minderåriga).
Moore graf
En Moore -graf är en vanlig graf för vilken Moore -gränsen uppfylls exakt. Moore -gränsen är en ojämlikhet som rör graden, diametern och ordningen på en graf, bevisad av Edward F. Moore . Varje Moore -graf är en bur.
multigraf
En multigraf är en graf som tillåter flera adjakenser (och ofta självslingor); en graf som inte krävs för att vara enkel.
multipel närhet
En multipel adjacency eller multipel kant är en uppsättning med mer än en kant som alla har samma slutpunkter (i samma riktning, när det gäller riktade grafer). En graf med flera kanter kallas ofta en multigraf.
mångfald
Multipliciteten av en kant är antalet kanter i en multipel adjacency. Mångfaldet i en graf är den maximala mångfalden av någon av dess kanter.

N

N
1. För notering för öppna och slutna stadsdelar, se grannskap .
2. Ett n används ofta (särskilt inom datavetenskap) för att ange antalet hörn i en given graf.
granne
granne
En toppunkt som ligger intill en viss toppunkt.
grannskap
grannskap
Det öppna grannskapet (eller grannskapet) för en toppunkt v är subgrafen som induceras av alla hörn som gränsar till v . Det stängda grannskapet definieras på samma sätt men inkluderar även v själv. Det öppna grannskapet v i G kan betecknas N G ( v ) eller N ( v ) , och det stängda grannskapet kan betecknas N G [ v ] eller N [ v ] . När öppenhet eller stängning av ett grannskap inte specificeras antas det vara öppet.
nätverk
En graf där attribut (t.ex. namn) är associerade med noder och/eller kanter.
nod
En synonym för vertex .
icke-kant
En icke-kant eller antikant är ett hörnpar som inte ligger intill varandra; kanterna på komplementgrafen.
nollgraf
Se tomt diagram .

O

udda
1. En udda cykel är en cykel vars längd är udda. Den udda omkretsen för en icke-bipartit graf är längden på dess kortaste udda cykel. Ett udda hål är ett speciellt fall av en udda cykel: en som induceras och har fyra eller flera hörn.
2. En udda hörn är en hörn vars grad är udda. Genom handskakande lemma har varje ändlig oriktad graf ett jämnt antal udda hörn.
3. Ett udda öra är en enkel väg eller enkel cykel med ett udda antal kanter, som används vid udda öronnedbrytningar av faktorkritiska grafer; se örat .
4. Ett udda ackord är en kant som förbinder två hörn som är ett udda avstånd från varandra i en jämn cykel. Udda ackord används för att definiera starkt ackordgrafer .
5. Ett udda diagram är ett specialfall av en Kneser -graf , som har en hörnpunkt för varje ( n -1 ) -elementundermängd av en (2 n -1 ) -elementuppsättning, och en kant som förbinder två delmängder när deras motsvarande uppsättningar är osammanhängande.
öppen
1. Se grannskap .
2. Se promenad .
beställa
1. Ordningen för en graf G är antalet hörn, | V ( G ) | . Variabeln n används ofta för denna mängd. Se även storlek , antal kanter.
2. En typ av logik i grafer ; se första ordningen och andra ordningen .
3. En ordning eller ordning av en graf är ett arrangemang av dess hörn i en sekvens, särskilt i sammanhanget med topologisk ordning (en ordning för en riktad acyklisk graf där varje kant går från en tidigare toppunkt till en senare toppunkt i ordningen ) och degenerationsordning (en ordning där varje hörn har minsta grad i den inducerade subgrafen av den och alla senare hörn).
4. För ordning av en fristad eller bramble, se fristad och bramble .
orientering
orienterad
1. En orientering av en oriktad graf är en tilldelning av riktningar till dess kanter, vilket gör den till en riktad graf. En orienterad graf är en som har tilldelats en orientering. Så till exempel är ett polytree ett orienterat träd; det skiljer sig från ett riktat träd (en arborescens) genom att det inte finns något krav på konsistens i dess kanter. Andra speciella typer av orientering inkluderar turneringar , orienteringar av kompletta grafer; starka orienteringar , orienteringar som är starkt sammankopplade; acykliska orienteringar , orienteringar som är acykliska; Eulerian orienteringar , orienteringar som är Eulerian; och transitiva orienteringar , riktningar som är transitivt stängda.
2. Orienterad graf, som används av vissa författare som en synonym för en riktad graf .
examen
Se examen .
yttre
Se ansikte .
yttre plan
En yttre plan graf är en graf som kan bäddas in i planet (utan korsningar) så att alla hörn är på grafens yttre yta.

P

väg
En väg kan antingen vara en promenad eller en promenad utan upprepade hörn och följaktligen kanter (även kallad en enkel väg), beroende på källan. Viktiga specialfall inkluderar inducerade vägar och kortaste vägar .
vägnedbrytning
En vägnedbrytning av en graf G är en trädnedbrytning vars underliggande träd är en väg. Dess bredd definieras på samma sätt som för trädnedbrytningar, som en mindre än storleken på den största påsen. Bredden på någon väg sönderdelning av minst G är pathwidth av G .
vägbredd
Den pathwidth av en graf G är den minsta bredden på en bana sönderdelning av G . Det kan också definieras i termer av klicken antalet intervall avslutad G . Det är alltid mellan bandbredden och G -bredden . Det är också känt som intervalltjocklek, toppunktseparationsnummer eller nodsökningsnummer.
hängsmycke
Se blad .
perfekt
1. Ett perfekt diagram är ett diagram där det kromatiska talet i varje inducerad delgraf är lika med klickantalet. Den perfekta grafsatsen och den starka perfekta grafsatsen är två satser om perfekta grafer, den förra bevisar att deras komplement också är perfekta och den senare visar att de är exakt graferna utan udda hål eller antihål.
2. En perfekt ordningsbar graf är en graf vars hörn kan ordnas på ett sådant sätt att en girig färgalgoritm med denna ordning optimalt färgar varje inducerad subgraf. De perfekt beställbara graferna är en underklass av de perfekta graferna.
3. En perfekt matchning är en matchning som mättar varje toppunkt; se matchning .
4. En perfekt 1-faktorisering är en uppdelning av kanterna på en graf i perfekta matchningar så att var och en av matchningarna bildar en Hamiltonian cykel.
kringutrustning
1. En perifer cykel eller icke-separerande cykel är en cykel med högst en bro.
2. En perifer vertex är en vertex vars excentricitet är maximal. I ett träd måste detta vara ett blad.
Petersen
1.   Julius Petersen (1839–1910), dansk grafteoretiker.
2. Petersen-grafen , en 10-toppig 15-kantig graf som ofta används som ett motexempel.
3.   Petersens teorem om att varje brygglöst kubikgraf har en perfekt matchning.
plan
Ett plant diagram är en graf som har en inbäddning i det euklidiska planet. Ett plandiagram är ett plant diagram för vilket en viss inbäddning redan har fixats. En k -plan graf är en som kan ritas i planet med högst k korsningar per kant.
polytree
Ett polytree är ett orienterat träd; ekvivalent, en riktad acyklisk graf vars underliggande oriktade graf är ett träd.
kraft
1. En grafeffekt G k för en graf G är en annan graf på samma toppunktsuppsättning; två hörn är intill varandra i G k när de är på avstånd som mest k i G . En lövkraft är ett närbesläktat koncept, härledt från ett träds kraft genom att ta subgrafen som induceras av trädets löv.
2.   Effektgrafanalys är en metod för att analysera komplexa nätverk genom att identifiera klickar, cyklar och stjärnor i nätverket.
3.   Maktlagar i gradfördelningarna av skalfria nätverk är ett fenomen där antalet hörn för en given grad är proportionellt mot graden av graden.
företrädare
En toppunkt som kommer före en viss toppunkt i en riktad väg .
rätt
1. En riktig subgraf är en subgraf som tar bort minst en toppunkt eller kant relativt hela grafen; för ändliga grafer är korrekta subgrafer aldrig isomorfa för hela grafen, men för oändliga grafer kan de vara.
2. En korrekt färgning är en tilldelning av färger till hörnen på en graf (en färgning) som tilldelar olika färger till slutpunkterna för varje kant; se färg .
3. Ett korrekt intervalldiagram eller korrekt cirkelbågsdiagram är ett snittdiagram av en samling intervall eller cirkelbågar (respektive) så att inget intervall eller en båge innehåller ett annat intervall eller en båge. Korrekta intervalldiagram kallas också enhetsintervalldiagram (eftersom de alltid kan representeras av enhetsintervall) eller likgiltighetsgrafer.
fast egendom
En grafegenskap är något som kan vara sant för vissa grafer och falskt för andra, och det beror bara på grafstrukturen och inte på tillfällig information som etiketter. Grafegenskaper kan likvärdigt beskrivas i termer av grafer (graferna som har en given egenskap). Mer generellt kan en grafegenskap också vara en funktion av grafer som återigen är oberoende av tillfällig information, såsom storleken, ordningen eller graden av en graf; denna mer allmänna definition av en egenskap kallas också en invariant av grafen.
pseudoforest
En pseudoforest är en oriktad graf där varje ansluten komponent har högst en cykel, eller en riktad graf där varje toppunkt har högst en utgående kant.
pseudograf
En pseudograf är en graf eller multigraf som tillåter självslingor.

F

kvasi-linjediagram
Ett kvasi-linjediagram eller lokalt medbipartit-diagram är ett diagram där det öppna grannskapet för varje hörn kan delas upp i två klick. Dessa grafer är alltid klofria och de inkluderar som ett specialfall linjediagrammen . De används i strukturteorin för klofria grafer.
koger
En koger är en riktad multigraf, som används i kategoriteori . Kanterna på en koger kallas pilar.

R

radie
Radien för en graf är den lägsta excentriciteten för alla hörn.
Ramanujan
En Ramanujan -graf är en graf vars spektrala expansion är så stor som möjligt. Det vill säga, det är en d -regelbunden graf, så att den näst största egenvärdet för dess adjacensmatris är som mest .
stråle
En stråle, i en oändlig graf, är en oändlig enkel väg med exakt en slutpunkt. De ändar av en graf är ekvivalensklasser av strålar.
nåbarhet
Möjligheten att komma från en toppunkt till en annan inom ett diagram .
nås
Har en bekräftande nåbarhet . Ett toppunkt y sägs nås från en toppunkt x om det finns en väg från x till y .
igenkännlig
I samband med rekonstruktionstanken är en grafegenskap igenkännlig om dess sanning kan bestämmas från grafens däck. Många grafegenskaper är kända för att vara igenkännbara. Om rekonstruktionstanken är sann känns alla grafegenskaper igen.
rekonstruktion
Den rekonstruktion hypotes säger att varje oriktad graf G är unikt bestäms av dess däck , en multimängd av grafer som bildas genom att avlägsna en vertex från G på alla möjliga sätt. I detta sammanhang är rekonstruktion bildandet av en graf från dess däck.
rektangel
En enkel cykel som består av exakt fyra kanter och fyra hörn.
regelbunden
En graf är d -regelbunden när alla dess hörn har grad d . En vanlig graf är en graf som är d -regelbunden för vissa d .
vanlig turnering
En vanlig turnering är en turnering där grad är lika med grad för alla hörn.
omvänd
Se transponering .
rot
1. En angiven toppunkt i en graf, särskilt i riktade träd och rotade grafer .
2. Den omvända operationen till en grafeffekt : en k: a roten i en graf G är en annan graf på samma hörnuppsättning så att två hörn är intilliggande i G om och bara om de har avstånd högst k i roten.

S

andra beställning
Den andra ordningens logik för grafer är en form av logik där variabler kan representera hörn, kanter, uppsättningar hörn och (ibland) uppsättningar av kanter. Denna logik inkluderar predikat för att testa om en toppunkt och kant är infallande, liksom om en toppunkt eller kant tillhör en uppsättning. Att skilja från första ordningens logik, där variabler endast kan representera hörn.
mättad
Se matchning .
söknummer
Nodsökningsnummer är en synonym för sökvägbredd .
självslinga
Synonym för loop .
skiljande hörn
Se artikulationspunkten .
separationsnummer
Vertex -separationsnummer är en synonym för vägbredd .
enkel
1. En enkel graf är en graf utan slingor och utan flera adjacenser. Det vill säga, varje kant förbinder två distinkta slutpunkter och inga två kanter har samma slutpunkter. En enkel kant är en kant som inte är en del av en multipel adjacency. I många fall antas graferna vara enkla om inte annat anges.
2. En enkel väg eller en enkel cykel är en väg eller cykel som inte har några upprepade hörn och följaktligen inga upprepade kanter.
handfat
En diskbänk, i en riktad graf, är en toppunkt utan utgående kanter (ut-grad är lika med 0).
storlek
Storleken på en graf G är antalet kanter, | E ( G ) | . Variabeln m används ofta för denna mängd. Se även ordning , antal hörn.
småvärldsnätverk
Ett småvärldsnätverk är en graf där de flesta noder inte är grannar till varandra, men de flesta noder kan nås från varannan nod med ett litet antal hopp eller steg. Specifikt definieras ett småvärldsnätverk som ett diagram där det typiska avståndet L mellan två slumpmässigt valda noder (antalet steg som krävs) växer proportionellt mot logaritmen för antalet noder N i nätverket
snark
En snark är en enkel, ansluten, brygglös kubikgraf med kromatiskt index lika med 4.
källa
En källa, i en riktad graf, är en toppunkt utan inkommande kanter (grad är lika med 0).
Plats
I algebraisk grafteori kan flera vektorutrymmen över det binära fältet associeras med en graf. Var och en har uppsättningar av kanter eller hörn för sina vektorer och symmetrisk skillnad av uppsättningar som sin vektorsumma -operation. Den kant utrymmet är utrymmet för alla olika typer av kanter och vertex utrymmet är utrymmet för alla olika typer av hörn. Den skurna utrymmet är ett underrum av kanten utrymme som har de skurna-uppsättningar grafen som sina element. Den cykel utrymme har Eulerian spänner subgrafer som dess element.
nyckel
En skiftnyckel är en (vanligtvis gles) graf vars kortaste vägavstånd är ungefärliga dem i ett tätt diagram eller annat metriskt utrymme. Variationer inkluderar geometriska nycklar , grafer vars hörn är punkter i ett geometriskt utrymme; trädnycklar , spännträd i en graf vars avstånd är ungefärliga grafavstånden, och grafnycklar, glesa undergrafer av en tät graf vars avstånd är ungefärliga med den ursprungliga grafens avstånd. En girig skiftnyckel är en grafnyckel konstruerad av en girig algoritm, vanligtvis en som betraktar alla kanter från kortast till längst och behåller de som behövs för att bevara avstånds -approximationen.
spänner över
En delgraf spänner över när den innehåller alla hörn i den givna grafen. Viktiga fall inkluderar spänning av träd , spänning av subgrafer som är träd och perfekta matchningar , spänner över subgrafer som är matchningar. En spännande subgraf kan också kallas en faktor , särskilt (men inte bara) när den är vanlig.
gles
En gles graf är en som har få kanter i förhållande till antalet hörn. I vissa definitioner bör samma egenskap också gälla för alla delgrafer av den givna grafen.
spektral-
spektrum
Spektrumet för en graf är samlingen av egenvärden för dess adjacensmatris. Spektral grafteori är den gren av grafteorin som använder spektra för att analysera grafer. Se även spektral expansion .
dela
1. Ett delat diagram är ett diagram vars hörn kan delas upp i en klick och en oberoende uppsättning. En relaterad klass av grafer, de dubbla delade graferna, används för att bevisa den starka perfekta grafsatsen.
2. En delning av ett godtyckligt diagram är en uppdelning av dess hörn i två icke -fördelade delmängder, så att kanterna som spänner över detta snitt bildar en komplett tvåpartsundersökning. Delarna i en graf kan representeras av en trädstruktur som kallas dess delade sönderdelning . En delning kallas en stark splittring när den inte korsas av någon annan delning. En delning kallas nontrivial när båda sidorna har mer än en toppunkt. En graf kallas primtal när den inte har några icke -privata delningar.
fyrkant
1. kvadraten på en graf G är den graf effekten G 2 ; i andra riktningen är G kvadratroten av G 2 . Den halv-kvadrat av en tvådelad graf är subgraf av den fyrkantiga inducerad av en sida av bidelning.
2. En kvadrat är en plan graf som kan ritas så att alla avgränsade ytor är 4-cykler och alla hörn med grad ≤ 3 tillhör ytterytan.
3. Ett fyrkantigt rutdiagram är ett gallerdiagram som definieras från punkter i planet med heltalskoordinater anslutna med kanter på längden.
stabil
En stabil uppsättning är en synonym för en oberoende uppsättning .
stjärna
En stjärna är ett träd med en inre toppunkt; på motsvarande sätt är det en komplett bipartit graf K 1, n för några n ≥ 2 . Specialfallet med en stjärna med tre blad kallas en klo.
styrka
Det styrkan av en graf är minimiförhållandet mellan antalet kanter som avlägsnats från grafen till komponenter skapas, över alla möjliga flyttningar; det är analogt med seghet, baserat på avlägsnande av vertex.
stark
1. För stark anslutning och starkt anslutna komponenter i riktade grafer, se ansluten och komponent . En stark orientering är en orientering som är starkt sammankopplad; se orientering .
2. För den starka perfekta grafsatsen , se perfekt .
3. En starkt vanlig graf är en vanlig graf där varannan intilliggande hörn har samma antal delade grannar och varannan icke-intilliggande hörn har samma antal delade grannar.
4. Ett starkt ackordgraf är ett ackorddiagram där varje jämn cykel med längd sex eller fler har ett udda ackord.
5. En starkt perfekt graf är en graf där varje inducerad subgraf har en oberoende uppsättning som uppfyller alla maximala klick. De Meyniel grafer kallas också "mycket starkt perfekt grafer" eftersom i dem, tillhör varje vertex till en sådan självständig uppsättning.
underskog
En undersökning av en skog .
undergraf
En subgraf av en graf G är en annan graf som bildas från en delmängd av hörnen och kanterna på G . Vertex -delmängden måste inkludera alla slutpunkter för kantundermängden, men kan också inkludera ytterligare hörn. En spännande subgraf är en som inkluderar alla hörn i grafen; en inducerad subgraf är en som inkluderar alla kanter vars slutpunkter tillhör topp -delmängden.
delträd
Ett delträd är en ansluten subgraf av ett träd. Ibland, för rotade träd, definieras subtrees som en speciell typ av ansluten subgraf, bildad av alla hörn och kanter som kan nås från en vald toppunkt.
efterträdare
En toppunkt som kommer efter en given toppunkt i en riktad väg .
superkoncentrator
En superkoncentrator är en graf med två utsedda och lika stora delmängder av hörn I och O , så att det för varje två lika stora delmängder S av I och T O finns en familj av sammanhängande vägar som förbinder varje hörn i S med en topp i T . Vissa källor kräver dessutom att en superkoncentrator är en riktad acyklisk graf, med I som dess källor och O som dess sänkor.
supergraf
En graf som bildas genom att lägga till hörn, kanter eller båda till en given graf. Om H är en subgraf av G , då G är en supergraph av H .

T

theta
1. En theta -graf är sammanslutningen av tre internt sammanfogade (enkla) banor som har samma två distinkta ändhörnor.
2. Theta -grafen för en samling punkter i det euklidiska planet konstrueras genom att konstruera ett system av kottar som omger varje punkt och lägga till en kant per kon, till den punkt vars projektion på en central stråle av konen är minsta.
3. Lovász -talet eller Lovász -theta -funktionen för en graf är en grafvariariant relaterad till klickantalet och det kromatiska talet som kan beräknas i polynomtid med semidefinit programmering.
topologisk
1. En topologisk graf är en representation av hörnens och kanterna på en graf med punkter och kurvor i planet (inte nödvändigtvis att undvika korsningar).
2.   Topologisk grafteori är studiet av grafinbäddningar.
3.   Topologisk sortering är det algoritmiska problemet med att ordna en riktad acyklisk graf i en topologisk ordning, en toppunktsekvens så att varje kant går från en tidigare toppunkt till en senare toppunkt i sekvensen.
helt frånkopplad
Synonym för kantlös .
Turné
Ett stängt spår, en promenad som börjar och slutar vid samma hörn och har inga upprepade kanter. Euler -turer är turer som använder alla grafkanter; se Eulerian .
turnering
En turnering är en orientering av ett komplett diagram; det vill säga, det är en riktad graf så att varannan hörn är ansluten med exakt en riktad kant (går bara i en av de två riktningarna mellan de två hörnen).
spårbar
En spårbar graf är en graf som innehåller en hamiltons väg.
spår
En promenad utan upprepade kanter.
transitiv
Har att göra med den transitiva egenskapen . Den transitiva stängningen av en given riktad graf är en graf på samma toppunktsuppsättning som har en kant från en toppunkt till en annan när den ursprungliga grafen har en väg som förbinder samma två hörn. En transitiv reduktion av en graf är en minimal graf med samma transitiva stängning; riktade acykliska grafer har en unik transitiv reduktion. En transitiv orientering är en orientering av en graf som är dess egen transitiva stängning; den existerar endast för jämförbarhetsgrafer .
införliva
Den transponering graf av en given riktad graf är en graf på samma vertex, med varje kant reverseras i riktning. Det kan också kallas omvänd eller omvänd av grafen.
träd
1. Ett träd är en oriktad graf som är både ansluten och acyklisk, eller en riktad graf där det finns en unik promenad från en toppunkt (trädets rot) till alla återstående hörn.
2. Ett k -träd är ett diagram som bildas genom att limma ( k + 1) -cliques ihop på delade k -cliques. Ett träd i vanlig mening är ett 1 -träd enligt denna definition.
trädets sönderdelning
Ett trädets sönderdelning av en graf G är ett träd vars noder är märkta med uppsättningar av hörn av G ; dessa uppsättningar kallas påsar. För varje hörn v måste påsarna som innehåller v framkalla ett träd av trädet, och för varje kant uv måste det finnas en påse som innehåller både u och v . Bredden på ett trädets sönderdelning är en mindre än det maximala antalet hörn i någon av dess påsar; den treewidth av G är bredden av något träd sönderdelning av minst G .
trädbredd
Den treewidth av en graf G är den minsta bredden av ett träd sönderdelning av G . Den kan också definieras i termer av klick antalet en ackord fullbordan av G , i storleksordningen av en oas av G , eller i storleksordningen av en bramble av G .
triangel
En cykel med längd tre i en graf. En triangelfri graf är en oriktad graf som inte har några triangeldelgrafer.
Turán
1.   Pál Turán
2. En Turán -graf är en balanserad komplett flerdelad graf.
3.   Turáns sats säger att Turán-grafer har det maximala antalet kanter bland alla klickfria grafer i en given ordning.
4.   Turáns tegelfabriksproblem ber om minsta antal korsningar i en ritning av en komplett tvåpartig graf.

U

ostyrd
En oriktad graf är en graf där de två slutpunkterna för varje kant inte skiljs från varandra. Se även regisserad och blandad . I en blandad graf är en oriktad kant återigen en där slutpunkterna inte skiljer sig från varandra.
enhetlig
En hypergraf är k -uniform när alla dess kanter har k -slutpunkter, och enhetlig när den är k -uniform för vissa k . Exempelvis är vanliga grafer samma som 2 -enhetliga hypergrafer.
universell
1. En universell graf är en graf som innehåller som undergrafer alla grafer i en given graffamilj eller alla grafer av en given storlek eller ordning inom en given graffamilj.
2. En universell hörnpunkt (även kallad en spets eller dominerande toppunkt) är en hörnpunkt som ligger intill varannan toppunkt i grafen. Till exempel har hjulgrafer och anslutna tröskeldiagram alltid en universell toppunkt.
3. I grafikens logik kan en toppunkt som är universellt kvantifierad i en formel kallas en universell toppunkt för den formeln.
oviktad graf
En graf vars hörn och kanter s inte har tilldelats vikt s ; motsatsen till en vägd graf .

V

V
Se toppunktsset .
valens
Synonym för examen .
vertex
En toppunkt (plural hörn) är (tillsammans med kanter) en av de två grundenheterna ur vilka grafer är konstruerade. Hörn av grafer anses ofta vara atomföremål, utan intern struktur.
hörnskärning
separationsuppsättning
En uppsättning hörn vars avlägsnande kopplar den grafen . Ett snitt med en vertex kallas en artikuleringspunkt eller cut vertex .
toppunktsset
Uppsättningen av hörn för en given graf G , ibland betecknad med V ( G ) .
hörn
Se toppunkt .
Vizing
1.   Vadim G. Vizing
2.   Vizing's sats om att det kromatiska indexet är högst en mer än maxgraden.
3.   Vizing's gissning om dominerande antalet kartesiska produkter av grafer.
volym
Summan av graderna i en uppsättning hörn.

W

W
Bokstaven W används i notation för hjulgrafer och väderkvarngrafer . Notationen är inte standardiserad.
Wagner
1.   Klaus Wagner
2. Wagner-grafen , en Möbius-stege med åtta vertex.
3.   Wagners sats som karakteriserar plana grafer av deras förbjudna minderåriga.
4. Wagners sats som kännetecknar K 5 -minorfria grafer.
promenad
En promenad är en ändlig eller oändlig sekvens av kanter som sammanfogar en sekvens av hörn . Promenader kallas också ibland kedjor . En promenad är öppen om dess första och sista hörn skiljer sig åt och stängs om de upprepas.
svagt ansluten
En riktad graf kallas svagt ansluten om alla riktade kanter ersätts med oriktade kanter ger en ansluten (oriktad) graf.
vikt
Ett numeriskt värde, tilldelat som en etikett till en toppunkt eller kant på ett diagram. Vikten av en undergraf är summan av vikten av hörn eller kanter inom den undergrafen.
viktad graf
En graf vars hörn eller kant s har tilldelats vikt s ; mer specifikt har en vertexvägd graf vikter på sina hörn och en kantvägd graf har vikter på sina kanter.
välfärgade
En välfärgad graf är en graf vars alla giriga färgämnen använder samma antal färger.
väl täckt
En väl täckt graf är en graf vars alla maximala oberoende uppsättningar har samma storlek.
hjul
Ett hjuldiagram är ett diagram som bildas genom att lägga till en universell toppunkt till en enkel cykel.
bredd
1. En synonym för degeneration .
2. För andra grafinvarianter som kallas bredd, se bandbredd , grenbredd , klickbredd , vägbredd och trädbredd .
3. Bredden på en trädsönderdelning eller vägnedbrytning är en mindre än den maximala storleken på en av dess påsar och kan användas för att definiera trädbredd och vägbredd.
4. Bredden på en riktad acyklisk graf är den maximala kardinaliteten hos en antikedja.
väderkvarn
En väderkvarngraf är sammanslutningen av en samling klickor, alla i samma ordning som varandra, med en gemensam hörn som tillhör alla klickar och alla andra hörn och kanter är distinkta.

Se även

Referenser