Förbjuden grafkarakterisering - Forbidden graph characterization
I grafteorin , en gren av matematik, kan många viktiga familjer av grafer beskrivas med en begränsad uppsättning enskilda grafer som inte tillhör familjen och ytterligare utesluter alla grafer från familjen som innehåller någon av dessa förbjudna grafer som (inducerad) subgraf eller mindre. Ett prototypiskt exempel på detta fenomen är Kuratowskis sats , som säger att en graf är plan (kan ritas utan korsningar i planet) om och bara om den inte innehåller någon av två förbjudna grafer, hela diagrammet K 5 och den fullständiga bipartiet diagram K 3,3 . För Kuratowskis teorem är begreppet inneslutning begreppet graf-homeomorfism , där en indelning av en graf framträder som en subgraf av den andra. Således har varje graf antingen en plan ritning (i vilket fall den tillhör familjen plana grafer) eller så har den en indelning av en av dessa två grafer som en undergraf (i vilket fall den inte tillhör de plana graferna).
Definition
Mer allmänt är en förbjuden grafkarakterisering en metod för att specificera en familj av diagram , eller hypergraph , strukturer, genom att specificera understrukturer som är förbjudna att existera inom någon graf i familjen. Olika familjer varierar beroende på vad som är förbjudet . I allmänhet, en struktur G är en medlem av en familj om och endast om ett förbjudet underkonstruktion är inte ingår i G . Den förbjudna underkonstruktionen kan vara en av:
- undergrafer , mindre grafer erhållna från delmängder av hörn och kanter i en större graf,
- inducerade underbilder , mindre grafer erhållna genom att välja en delmängd av topparna och använda alla kanter med båda slutpunkterna i den delmängden,
- homeomorfa underbilder (även kallade topologiska minderåriga ), mindre grafer erhållna från underbilder genom att kollapsa banor för grad två-hörn till enstaka kanter, eller
- mindreåriga , mindre grafer erhållna från underbilder genom godtyckliga kantkontraktioner .
Uppsättningen av strukturer som är förbjudna att tillhöra en viss graffamilj kan också kallas en hinderuppsättning för den familjen.
Förbjudna diagramkarakteriseringar kan användas i algoritmer för att testa om ett diagram tillhör en viss familj. I många fall är det möjligt att testa i polynomial tid om en given graf innehåller någon av medlemmarna i obstruktionssatsen, och därför om den tillhör den familj som definieras av den hindren.
För att en familj ska ha en förbjuden grafkaraktärisering, med en viss typ av underkonstruktion, måste familjen vara stängd under underkonstruktioner. Det vill säga att varje underkonstruktion (av en viss typ) av ett diagram i familjen måste vara ett annat diagram i familjen. På samma sätt, om ett diagram inte är en del av familjen, måste alla större grafer som innehåller det som en underkonstruktion också uteslutas från familjen. När detta är sant finns det alltid en hinderuppsättning (den uppsättning diagram som inte finns i familjen men vars mindre understrukturer alla tillhör familjen). Men för vissa föreställningar om vad en underkonstruktion är kan detta hinderuppsättning vara oändligt. Satsen Robertson – Seymour bevisar att, för det särskilda fallet med mindreåriga , har en familj som är stängd under minderåriga alltid en begränsad hinderuppsättning.
Lista över förbjudna karakteriseringar för grafer och hypergrafer
| Familj | Hinder | Relation | Referens |
|---|---|---|---|
| Skogar | öglor, par parallella kanter och cykler i alla längder | subgraf | Definition |
| en slinga (för multigrafer) eller en triangel K 3 (för enkla grafer) | diagram mindre | Definition | |
| Klofria grafer | stjärna K 1,3 | inducerad subgraf | Definition |
| Jämförbarhetsdiagram | inducerad subgraf | ||
| Triangelfria grafer | triangel K 3 | inducerad subgraf | Definition |
| Plana diagram | K 5 och K 3,3 | homeomorf subgraf | Kuratowskis sats |
| K 5 och K 3,3 | diagram mindre | Wagners sats | |
| Ytterplanära grafer | K 4 och K 2,3 | diagram mindre | Diestel (2000) , s. 107 |
| Yttre 1-plana grafer | sex förbjudna minderåriga | diagram mindre | Auer et al. (2013) |
| Grafer av fasta släkter | en begränsad hinderuppsättning | diagram mindre | Diestel (2000) , s. 275 |
| Apex-diagram | en begränsad hinderuppsättning | diagram mindre | |
| Länkfritt inbäddade diagram | Familjen Petersen | diagram mindre | |
| Bipartitdiagram | udda cykler | subgraf | |
| Akkordala grafer | cykler med längd 4 eller mer | inducerad subgraf | |
| Perfekta diagram | cykler av udda längd 5 eller mer eller deras komplement | inducerad subgraf | |
| Linjediagram över grafer | nio förbjudna underbilder (listade här ) | inducerad subgraf | |
| Grafföreningar av kaktusdiagram | den fyra-toppiga diamantgrafen bildad genom att ta bort en kant från hela grafen K 4 | diagram mindre | |
| Stegdiagram | K 2,3 och dess dubbla diagram | homeomorf subgraf | |
| Dela grafer | inducerad subgraf | ||
| 2-ansluten serie – parallell ( trebredd ≤ 2, grenbredd ≤ 2) | K 4 | diagram mindre | Diestel (2000) , s. 327 |
| Trebredd ≤ 3 | K 5 , oktaeder , femkantigt prisma , Wagnerdiagram | diagram mindre | |
| Grenbredd ≤ 3 | K 5 , oktaeder , kub , Wagnerdiagram | diagram mindre | |
| Komplementreducerbara grafer (grafer) | 4-spetsväg P 4 | inducerad subgraf | |
| Avgörande perfekta grafer | 4-vertex banan P 4 och 4-vertex cykel C 4 | inducerad subgraf | |
| Tröskeldiagram | 4-vertex bana P 4 , 4-vertex cykel C 4 , och komplement av C 4 | inducerad subgraf | |
| Linjediagram över 3-enhetliga linjära hypergrafer | en begränsad lista över förbjudna inducerade underbilder med minsta grad minst 19 | inducerad subgraf | |
| Linjediagram över k- enhetliga linjära hypergrafer, k > 3 | en begränsad lista över förbjudna inducerade underbilder med minsta kantgrad minst 2 k 2 - 3 k + 1 | inducerad subgraf | |
| Grafer AY-reducerbar till en enda vertex | en begränsad lista med minst 68 miljarder olika (1,2,3) klickbelopp | diagram mindre | |
| Allmänna satser | |||
| En familj definierad av en inducerad ärftlig egendom | en, eventuellt icke-ändlig, hinderuppsättning | inducerad subgraf | |
| En familj som definieras av en mindre ärftlig egendom | en begränsad hinderuppsättning | diagram mindre | Theorem från Robertson – Seymour |
