grafo nulo - Null graph

No matemático campo da teoria gráfico , o termo " gráfico nulo " pode referir-se à ordem - de zero gráfico , ou alternativamente, para qualquer gráfico edgeless (o último é muitas vezes chamado um "gráfico vazio").

Fim de zero gráfico

Pedido de zero gráfico (gráfico nulo)
vértices	0
Arestas	0
circunferência	${\ Displaystyle \ infty}$
automorphisms	1
número cromático	0
índice cromático	0
Gênero	0
propriedades	Integral simétrica
Notação	${\ Displaystyle K_ {0}}$
Tabela de gráficos e parâmetros

O gráfico da ordem de zero , , é o único gráfico não tendo vértices (daí o seu fim é zero). Daqui resulta que também não tem arestas . Alguns autores excluir da consideração como um gráfico (seja por definição, ou mais simplesmente como uma questão de conveniência). Se a inclusão como um gráfico válido é útil depende do contexto. No lado positivo, decorre naturalmente dos habituais set-teórico definições de um gráfico (que é o par ordenado ( V , E ) para que os vértices e de borda define, V e E , são ambos vazia ), em provas que serve como uma caso de base natural para indução matemático , e semelhante, em recursivamente definidas estruturas de dados é útil para definir o caso base para recursão (por tratamento do nulo árvore como a criança de bordas ausentes em qualquer não-nulo árvore binária , cada binário não-nulo árvore tem exatamente dois filhos). No lado negativo, incluindo como um gráfico requer que muitas fórmulas bem definidos para propriedades de gráficos incluem excepções para isso (por exemplo, quer "contagem de todos os componentes fortemente ligados de um gráfico" torna-se "contagem de todos os não-nulos componentes fortemente ligados de um gráfico", ou a definição de gráficos ligados tem de ser modificado para incluir não K ₀ ). Para evitar a necessidade de tais excepções, é frequentemente assumido na literatura que o termo gráfico implica "do gráfico com pelo menos um vértice", a menos que de outro modo sugere contexto.${\ Displaystyle K_ {0}}$${\ Displaystyle K_ {0}}$${\ Displaystyle K_ {0}}$${\ Displaystyle K_ {0}}$${\ Displaystyle K_ {0}}$ ${\ Displaystyle K_ {0}}$${\ Displaystyle K_ {0}}$

Em teoria categoria , o gráfico de ordem-zero é, de acordo com algumas definições de "categoria de gráficos", o objecto inicial na categoria.

${\ Displaystyle K_ {0}}$cumpre ( vacuously ) a maioria das mesmas propriedades de gráficos básicos como o faz (o gráfico com um vértice e sem arestas). Como alguns exemplos, é de tamanho zero, ele é igual ao seu gráfico de complemento , uma floresta , e um gráfico planar . Pode considerar-se não dirigida , dirigida , ou mesmo ambos; quando considerado como indicado, que é um gráfico acíclico dirigido . E isso é tanto um grafo completo e um gráfico edgeless. No entanto, as definições para cada um destes propriedades gráfico vai variar dependendo se contexto permite . ${\ Displaystyle K_ {1}}$${\ Displaystyle K_ {0}}$ ${\ Displaystyle {\ overline {K_ {0}}}}$${\ Displaystyle K_ {0}}$

gráfico Edgeless

gráfico Edgeless (gráfico vazio, gráfico nulo)
vértices	n
Arestas	0
Raio	0
Diâmetro	0
circunferência	${\ Displaystyle \ infty}$
automorphisms	n!
número cromático	1
índice cromático	0
Gênero	0
propriedades	Integral simétrica
Notação	${\ Displaystyle {\ overline {K}} _ {n}}$
Tabela de gráficos e parâmetros

Para cada número natural n , o gráfico sem gume (ou gráfico vazio) de ordem n é o gráfico com n vértices e zero bordas. Um gráfico edgeless é ocasionalmente referido como um gráfico nulo em contextos onde o gráfico de ordem zero não é permitida.${\ Displaystyle {\ overline {K}} _ {n}}$

É um 0- regulares gráfico. A notação surge a partir do facto de que o n -vertex gráfico edgeless é o complemento do gráfico completo . ${\ Displaystyle {\ overline {K}} _ {n}}$ ${\ Displaystyle K_ {n}}$

Veja também

• Glossário de teoria gráfico
• grafo ciclo
• gráfico caminho

Notas

Referências

• Harary, F. and Read, R. (1973), "é o gráfico nulo um conceito sem sentido?", Gráficos e Combinatória (Conferência, George Washington University), Springer-Verlag, New York, NY.