Zerowy wykres - Null graph

W matematycznej dziedzinie teorii wykres , termin „ zerowy wykres ” może odnosić się albo do celu - zerowej wykresu , lub alternatywnie, w przypadku każdego pozbawionej krawędzi wykresu (ten ostatni jest czasami nazywany „pusty wykres”).

Zamówienie zera wykres

Kolejność zerowej wykresu (null wykres)
wierzchołki	0
Obrzeża	0
Obwód	${\ Displaystyle \ infty}$
automorfizmy	1
liczba chromatyczna	0
indeks chromatyczny	0
Rodzaj	0
Nieruchomości	integralną symetryczna
Notacja	${\ Displaystyle K_ {0}}$
Tabela wykresów i parametrów

Celu zerowej wykresu , jest unikalny wykres które nie mają wierzchołki (stąd ich porządek jest równa zero). Wynika stąd, że również nie ma krawędzi . Niektórzy autorzy wykluczyć z rozważań w postaci wykresu (albo z definicji, lub po prostu jako kwestia wygody). Czy tym , jak ważny wykres jest przydatna, zależy od kontekstu. Po dodatniej stronie, następuje w sposób naturalny od zwykłych zestawów-theoretic definicji wykresie (to uporządkowane pary ( V , E ), w których zestawy wierzchołków i krawędzi, V i E , oba puste ) w dowodach służy jako naturalny przypadek bazowy dla indukcji matematycznej , i podobnie, w rekurencyjnie zdefiniowanych struktur danych jest przydatna do określania przypadek bazowy dla rekursji (traktując pustego drzewa jako dziecko brakujących krawędzi w dowolnym niepuste drzewa binarnego , każdy niezerowe binarny drzewo ma dokładnie dwa dzieci). Negatywną stroną, w tym w postaci wykresu wymaga wiele dobrze określone wzory na właściwości wykres obejmują wyjątki dostępu (na przykład, zarówno „licząc wszystkie silnie związane komponenty wykresu” staje się „zliczeniu wszystkich niezerowych mocno połączone składniki wykres”lub określenie połączonych wykresów ma nie być modyfikowany w celu K, ₀ ). Aby uniknąć konieczności takich wyjątków, jest często w literaturze przyjmuje się, że termin wykres sugeruje „wykres z przynajmniej jednym wierzchołkiem” o ile kontekst nie sugeruje inaczej.${\ Displaystyle K_ {0}}$${\ Displaystyle K_ {0}}$${\ Displaystyle K_ {0}}$${\ Displaystyle K_ {0}}$${\ Displaystyle K_ {0}}$ ${\ Displaystyle K_ {0}}$${\ Displaystyle K_ {0}}$

W teorii kategorii wykres zamówień zero, według niektórych definicji „kategoria wykresach”, w początkowym obiektu w danej kategorii.

${\ Displaystyle K_ {0}}$niespełniająca ( próżniowo ), głównie te same podstawowe właściwości wykres podobnie jak (wykres z jednego wierzchołka i krawędzi). Kilka przykładów, jest wielkości zerowej jest równa jego wykres dopełniacza , w lesie , oraz płaską wykresie . Można uznać, nieukierunkowane , skierowane , a nawet obu; gdy rozpatrywana zgodnie ze wskazaniami, że jest skierowany acykliczny wykres . I to zarówno graf pełny i bez krawędzi wykresu. Jednakże, określenia dla każdej z tych właściwości wykres będzie się różnić w zależności od tego, czy kontekst pozwala . ${\ Displaystyle K_ {1}}$${\ Displaystyle K_ {0}}$ ${\ Displaystyle {\ overline {K_ {0}}}}$${\ Displaystyle K_ {0}}$

bezkrawędziowego wykres

Bezkrawędziowego wykres (pusty wykres, zero wykres)
wierzchołki	n
Obrzeża	0
Promień	0
Średnica	0
Obwód	${\ Displaystyle \ infty}$
automorfizmy	n!
liczba chromatyczna	1
indeks chromatyczny	0
Rodzaj	0
Nieruchomości	integralną symetryczna
Notacja	${\ Displaystyle {\ overline {k}} _ {n}}$
Tabela wykresów i parametrów

Dla każdej liczby naturalne n The bezkrawędziowego wykres (puste lub panel) w kolejności n jest wykres z n wierzchołków i zerowych krawędzi. Bez krawędzi wykresu jest czasami określany jako zerowy wykresie w sytuacjach, gdy wykres celu zerowania nie jest dozwolone.${\ Displaystyle {\ overline {k}} _ {n}}$

Jest to 0- regularny graf. Oznaczenie polega na tym, że brak -Vertex bezkrawędziowego wykres jest dopełnienie o pełnej wykresie . ${\ Displaystyle {\ overline {k}} _ {n}}$ ${\ Displaystyle K_ {n}}$

Zobacz też

• Słownik teorii wykres
• wykres cyklu
• wykres ścieżka

Uwagi

Referencje

• Harary, F. i czytać, R. (1973), "Czy zerowy wykres bezcelowe pojęcie?", Wykresy i Kombinatoryka (Konferencja, George Washington University), Springer-Verlag, New York, NY.