Noll graf - Null graph

I matematisk området för grafteori , termen " nollgraf " kan hänvisa antingen till order - noll graf , eller alternativt, till alla kantlösa graf (den senare kallas ibland en "tom graf").

Ordning-noll graf

Ordning-noll graf (noll graf)
hörn	0
Kanter	0
Omkrets	${\ displaystyle \ infty}$
automorfismer	1
Kromatiskt nummer	0
Kromatiskt index	0
Släkte	0
Egenskaper	Integrerad symmetrisk
Notation	${\ displaystyle K_ {0}}$
Tabell över grafer och parametrar

Den ordning-noll graf , , är den unika graf som har inga hörn (därav dess ordning är noll). Av detta följer att det inte heller har några kanter . Vissa författare utesluter från betraktande som en graf (antingen per definition eller enklare som en fråga om bekvämlighet). Huruvida det är användbart att inkludera som en giltig graf beror på sammanhang. På den positiva sidan följer naturligt från de vanliga setteoretiska definitionerna av en graf (det är det ordnade paret ( V , E ) för vilket topp- och kantuppsättningarna, V och E , båda är tomma ), i bevisen fungerar det som en naturlig bas fodral för matematisk induktion , och på liknande sätt, i rekursivt definierade datastrukturer är användbar för att definiera basfallet för rekursion (genom behandling av null trädet som barnet saknade kanter i varje icke-noll binärt träd , varje icke-noll binär trädet har exakt två barn). På den negativa sidan, inklusive som en graf kräver att många väldefinierade formler för grafegenskaper inkluderar undantag för den (till exempel, antingen "räknar alla starkt anslutna komponenter i en graf" blir "räknar alla icke-null starkt anslutna komponenter i en graf ", eller definitionen av anslutna grafer måste ändras för att inte inkludera K ₀ ). För att undvika behovet av sådana undantag antas det ofta i litteraturen att termen graf innebär "graf med minst en toppunkt" såvida inte sammanhang antyder något annat.${\ displaystyle K_ {0}}$${\ displaystyle K_ {0}}$${\ displaystyle K_ {0}}$${\ displaystyle K_ {0}}$${\ displaystyle K_ {0}}$ ${\ displaystyle K_ {0}}$${\ displaystyle K_ {0}}$

I kategoriteori är ordningsnollgrafen, enligt vissa definitioner av "kategori av grafer," det första objektet i kategorin.

${\ displaystyle K_ {0}}$uppfyller ( vakuum ) de flesta av samma grundläggande grafegenskaper som gör (grafen med en toppunkt och inga kanter). Som några exempel är storleken noll, den är lika med dess komplementgraf , en skog och en plan graf . Det kan betraktas som inriktad , riktad eller till och med båda; när det betraktas som riktat är det en riktad acyklisk graf . Och det är både en komplett graf och en kantlös graf. Definitionerna för var och en av dessa grafegenskaper kommer dock att variera beroende på om sammanhang tillåter . ${\ displaystyle K_ {1}}$${\ displaystyle K_ {0}}$ ${\ displaystyle {\ overline {K_ {0}}}}$${\ displaystyle K_ {0}}$

Edgeless graf

Ädelfri graf (tom graf, noll graf)
hörn	n
Kanter	0
Radie	0
Diameter	0
Omkrets	${\ displaystyle \ infty}$
automorfismer	n!
Kromatiskt nummer	1
Kromatiskt index	0
Släkte	0
Egenskaper	Integrerad symmetrisk
Notation	${\ displaystyle {\ overline {K}} _ {n}}$
Tabell över grafer och parametrar

För varje naturligt tal n är den kantlösa grafen (eller den tomma grafen) i ordningen n diagrammet med n hörn och nollkanter. En kantfri graf kallas ibland som en nollgraf i sammanhang där ordningsnollgrafen inte är tillåten.${\ displaystyle {\ overline {K}} _ {n}}$

Det är en regelbunden 0. Notationen kommer från det faktum att den n- vertex kantfria grafen är komplementet till den kompletta grafen . ${\ displaystyle {\ overline {K}} _ {n}}$ ${\ displaystyle K_ {n}}$

Se även

• Ordlista för grafteori
• Cykeldiagram
• Sökväg graf

anteckningar

referenser

• Harary, F. och Read, R. (1973), "Är nollgrafen ett meningslöst begrepp?", Grafer och kombinatorik (konferens, George Washington University), Springer-Verlag, New York, NY.