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
- Lista över grafteoriska ämnen
- Galleri med namngivna grafer
- Grafalgoritmer
- Ordlista över matematikområden