Grafegenskap

En exempelgraf, med egenskaperna att vara plan och vara ansluten , och med ordning 6, storlek 7, diameter 3, omkrets 3, vertexanslutning 1 och gradsekvens

<3, 3, 3, 2, 2, 1>

I grafteorin är en grafegenskap eller grafinvariant en egenskap hos grafer som endast beror på den abstrakta strukturen, inte på grafrepresentationer som speciella märkningar eller ritningar av grafen.

Definitioner

Medan grafritning och grafrepresentation är giltiga ämnen inom grafteori, för att bara fokusera på den abstrakta strukturen av grafer, definieras en grafegenskap som en egenskap som bevaras under alla möjliga isomorfismer av en graf. Det är med andra ord en egenskap hos själva grafen, inte för en specifik ritning eller representation av grafen. Informellt används termen "grafinvariant" för egenskaper uttryckta kvantitativt, medan "egenskap" vanligtvis syftar på beskrivande karakteriseringar av grafer. Till exempel är påståendet "grafen har inte hörn av grad 1" en "egenskap" medan "antalet hörn av grad 1 i en graf" är en "invariant".

Mer formellt är en grafegenskap en klass av grafer med egenskapen att två isomorfa grafer antingen tillhör klassen eller båda inte tillhör den. På motsvarande sätt kan en grafegenskap formaliseras med hjälp av klassens indikatorfunktion , en funktion från grafer till booleska värden som är sant för grafer i klassen och annars falskt; återigen, två isomorfa grafer måste ha samma funktionsvärde som varandra. En grafinvariant eller grafparameter kan på liknande sätt formaliseras som en funktion från grafer till en bredare klass av värden, såsom heltal, reella tal , talsekvenser eller polynom , som återigen har samma värde för två isomorfa grafer.

Fastigheters egenskaper

Många grafegenskaper fungerar väl med avseende på vissa naturliga delordningar eller förorder definierade på grafer:

En grafegenskap P är ärftlig om varje inducerad subgraf i en graf med egenskap P också har egenskapen P . Att till exempel vara en perfekt graf eller att vara en ackordsgraf är ärftliga egenskaper.
En grafegenskap är monoton om varje subgraf i en graf med egenskap P också har egenskap P . Att till exempel vara en tvådelad graf eller att vara en triangelfri graf är monotont. Varje monoton egenskap är ärftlig, men inte nödvändigtvis vice versa; till exempel är subgrafer av ackordsgrafer inte nödvändigtvis ackordala, så att vara en ackordsgraf är inte monotont.
En graph-egenskap är minor-closed om varje graph minor i en graf med egenskapen P också har egenskapen P . Att till exempel vara en plan graf är mindre-stängd. Varje mindre stängd egendom är monoton, men inte nödvändigtvis vice versa; till exempel är mindreåriga triangelfria grafer inte nödvändigtvis triangelfria.

Dessa definitioner kan utökas från egenskaper till numeriska invarianter av grafer: en grafinvariant är ärftlig, monoton eller mollsluten om funktionen som formaliserar invarianten bildar en monoton funktion från motsvarande partiella ordning på grafer till de reella talen.

Dessutom har grafinvarianter studerats med avseende på deras beteende med avseende på osammanhängande sammanslutningar av grafer:

En grafinvariant är additiv om, för alla två grafer G och H , värdet av invarianten på den disjunkta unionen av G och H är summan av värdena på G och på H . Till exempel är antalet hörn additivt.
En grafinvariant är multiplikativ om, för alla två grafer G och H , värdet av invarianten på den disjunkta föreningen av G och H är produkten av värdena på G och på H . Till exempel Hosoya-indexet (antal matchningar) multiplikativt.
En grafinvariant är maxning om, för alla två grafer G och H , värdet av invarianten på den disjunkta föreningen av G och H är det maximala av värdena på G och på H . Till exempel kromatiska numret max.

Dessutom kan grafegenskaper klassificeras efter vilken typ av graf de beskriver: om grafen är oriktad eller riktad , om egenskapen gäller multigrafer osv.

Värden av invarianter

Måluppsättningen för en funktion som definierar en grafinvariant kan vara en av :

Ett sanningsvärde, sant eller falskt, för indikatorfunktionen för en grafegenskap.
Ett heltal, till exempel antalet hörn eller kromatiskt tal för en graf.
Ett reellt tal , till exempel det kromatiska bråktalet för en graf.
En sekvens av heltal, till exempel gradsekvensen för en graf.
Ett polynom , till exempel Tutte-polynomet i en graf.

Grafinvarianter och grafisomorfism

Lättberäknade grafinvarianter är instrumentella för snabb igenkänning av grafisomorfism , eller snarare icke-isomorfism, eftersom för vilken invariant som helst, två grafer med olika värden inte (per definition) kan vara isomorfa. Två grafer med samma invarianter kan dock vara isomorfa eller inte.

En grafinvariant I ( G ) kallas komplett om identiteten av invarianterna I ( G ) och I ( H ) antyder isomorfismen hos graferna G och H. Att hitta en effektivt beräkningsbar sådan invariant (problemet med grafkanonisering ) skulle innebära en enkel lösning på det utmanande grafisomorfismproblemet . Men även polynomvärdade invarianter som det kromatiska polynomet är vanligtvis inte kompletta. Klografen och väggrafen på 4 hörn har båda samma kromatiska polynom, till exempel .

Exempel

Egenskaper

Heltalsinvarianter

Ordning , antalet hörn
Storlek , antalet kanter
Antal anslutna komponenter
Circuit rank , en linjär kombination av antalet kanter, hörn och komponenter
diameter , den längsta av de kortaste väglängderna mellan par av hörn
omkrets , längden på den kortaste cykeln
Vertex connectivity , det minsta antalet hörn vars borttagning kopplar bort grafen
Edge connectivity , det minsta antalet kanter vars borttagning kopplar bort grafen
Kromatiskt tal , det minsta antalet färger för hörnen i en korrekt färgning
Kromatiskt index , det minsta antalet färger för kanterna i en korrekt kantfärgning
Valbarhet (eller lista kromatiskt tal ), det minsta antalet k så att G är k-valbart
Independence number , den största storleken på en oberoende uppsättning hörn
Klicknummer , den största ordningen av en komplett subgraf
Arborisitet
Graf släkte
Sidonummer
Hosoya index
Wiener index
Colin de Verdière graf invariant
Boxicitet

Invarianter för reella tal

Sekvenser och polynom

Gradföljd
Grafspektrum
Karakteristiskt polynom för närliggande matris
Kromatiskt polynom , antalet $k$ -färgningar ses som en funktion av $k$
Tuttepolynom , en bivariat funktion som kodar mycket av grafens anslutningsmöjligheter

Se även

Ärftlig egendom
Logic of graphs , ett av flera formella språk som används för att specificera grafegenskaper
Topologiskt index , ett närbesläktat begrepp inom kemisk grafteori