Noll graf

Inom det matematiska fältet av grafteorin kan termen " nollgraf " hänvisa antingen till grafen ordning - noll , eller alternativt till vilken kantlös graf som helst (den senare kallas ibland en "tom graf").

Order-noll graf

Ordningsnoll-graf (noll-graf)
Vertices	0
Kanter	0
Omkrets	∞
Automorfismer	1
Kromatiskt nummer	0
Kromatiskt register	0
Genus	0
Egenskaper	Integral symmetrisk trädbredd -1
Notation	K0
Tabell över grafer och parametrar

Ordnings -noll-grafen , K ₀ , är den unika grafen som inte har några hörn (därav dess ordning är noll). Det följer att K ₀ inte heller har några kanter . Således är nollgrafen en vanlig graf med grad noll. Vissa författare utesluter K ₀ från att betraktas som en graf (antingen per definition, eller enklare som en bekvämlighetsfråga). Huruvida det är användbart att inkludera K ₀ som en giltig graf beror på sammanhanget. På den positiva sidan K ₀ naturligt av de vanliga mängdteoretiska definitionerna av en graf (det är det ordnade paret ( V , E ) för vilket vertex- och kantmängderna, V och E , båda är tomma ), i bevis den tjänar som ett naturligt basfall för matematisk induktion , och på liknande sätt, i rekursivt definierade datastrukturer är K ₀ användbar för att definiera basfallet för rekursion (genom att behandla nollträdet som kanter barnet till saknade i alla icke-null binära träd , varje icke- null binärt träd har exakt två barn). På den negativa sidan, att inkludera K ₀ som en graf kräver att många väldefinierade formler för grafegenskaper inkluderar undantag för det (till exempel, antingen "att räkna alla starkt anslutna komponenter i en graf" blir "att räkna alla icke-null starkt anslutna komponenter av en graf", eller så måste definitionen av kopplade grafer ändras så att den inte inkluderar K ₀ ). För att undvika behovet av sådana undantag antas det ofta i litteraturen att termen graf antyder "graf med minst en vertex" om inte sammanhanget antyder något annat.

I kategoriteori är ordning-noll-grafen, enligt vissa definitioner av "kategori av grafer", det initiala objektet i kategorin.

K ₀ uppfyller ( vakuöst ) de flesta av samma grundläggande grafegenskaper som K ₁ (grafen med en vertex och inga kanter). Som några exempel är K av ₀ storlek noll, det är lika med dess komplementgraf K ₀ , en skog och en plan graf . Det kan anses oriktat , regisserat eller till och med båda; när det anses som riktat är det en riktad acyklisk graf . Och det är både en komplett graf och en kantlös graf. Definitioner för var och en av dessa grafegenskaper kommer dock att variera beroende på om sammanhanget tillåter K ₀ .

Kantlös graf

Kantlös graf (tom graf, nollgraf)
Vertices	n
Kanter	0
Radie	0
Diameter	0
Omkrets	∞
Automorfismer	n !
Kromatiskt nummer	1
Kromatiskt index	0
Genus	0
Egenskaper	Integral symmetrisk
Notation	K n
Tabell över grafer och parametrar

För varje naturligt tal n är den kantlösa grafen (eller den tomma grafen) K _n av ordningen n grafen med n hörn och nollkanter. En kantlös graf kallas ibland för en noll-graf i sammanhang där ordning-noll-grafen inte är tillåten.

Det är en 0- vanlig graf. Beteckningen K _n härrör från det faktum att den n -vertex-kantlösa grafen är komplementet till hela grafen K _n .

Se även

• Ordlista för grafteori
• Cykeldiagram
• Väg graf

Anteckningar

• Harary, F. och Read, R. (1973), "Is the noll graph a pointless concept?", Graphs and Combinatorics (Conference, George Washington University), Springer-Verlag, New York, NY.