Grafo nulo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Grafo nulo
vértices 0
arestas 0
Automorfismos 1

No campo da matemática da teoria dos grafos, o grafo nulo ou o grafo vazio ou é o grafo sem nenhum vértice e (portanto) sem arestas, ou qualquer grafo sem arestas.

O grafo nulo (no sentido original) é o objeto inicial na categoria de grafos, de acordo com algumas definições de categoria de grafos. Não tendo nenhum vértice, o grafo nulo, portanto, também não tem componentes ligados. Assim, embora o grafo nulo seja uma floresta (um grafo sem ciclos), não é uma árvore, uma vez que as árvores têm componente ligados.

Grafo sem arestas[editar | editar código-fonte]

Grafo sem arestas
vértices n
arestas 0
Automorfismos n!
Número cromático 1
Propriedades Integral
Simétrico
Notação \bar K_n

Alguns autores entendem que um termo melhor para o último sentido (V, { }) para qualquer conjunto V é o mais explícito grafo sem arestas. Assim se reserva o termo grafo nulo para o primeiro sentido: um grafo sem quaisquer vértices. Outros, ainda, fazem essa distinção, aplicando o rótulo vazio para esses grafos sem arestas.

O grafo sem arestas de n-vértices é o grafo complementar para o grafo completo K_n, e por isso é comumente denotado como \bar K_n.

Mesmo que esta definição forneca uma base sólida para a definição de certas operações sobre grafos (por exemplo: decomposição) considerando-se grafos como conjuntos de vértices e arestas (V,E), esta definição levanta um problema na singularidade do elemento nulo dos grafos.