Um grafo G=(V, E) é conexo se existir um caminho entre qualquer par de vértices. Caso Contrário é desconexo – se há pelo menos um par de vértices que não está ligado a nenhuma cadeia (caminho).
Um grafo é planar se puder ser desenhado no plano sem que haja arestas se cruzando. Arestas se cruzam (cortam) se há interseção das linhas/arcos que as represen- tam em um ponto que não seja um vértice. – Tal desenho é chamado representação planar do grafo.
Um grafo é bipartido se e somente se ele não contém um ciclo ímpar. Portanto, um grafo bipartido não pode conter uma clique de tamanho ímpar. Um grafo é bipartido se e somente se ele é 2-colorível, (i.e. seu número cromático é menor ou igual a 2).
Portanto, para decidir se um grafo G é fortemente conexo, basta fazer buscas DFS (ou BFS), uma partir de cada vértice de G , e verificar se cada uma dessas buscas atinge todos os vértices.
Um grafo é fortemente conexo (= strongly connected = diconnected) se para qualquer par (v,w) de seus vértices existe um caminho de v a w e também um caminho de w para v. ... Em outras palavras, um grafo é fortemente conexo se o território de qualquer vértice é o conjunto de todos os vértices do grafo.
Em teoria dos grafos, um caminho em um grafo é uma sequência finita ou infinita de vértices conectados por uma sequência de arestas que, na maioria das definições, são todos diferentes uns dos outros. O primeiro vértice é chamado de vértice inicial e o último é chamado de vértice final.
Um grafo bipartido completo possui uma aresta para cada par de vértices vi ∈V1 e vj∈V2. Se n1 é o número de vértices em V1 e n2 é o número de vértices em V2, o grafo bipartido completo é denotado por Kn1,n2. Teorema 2 – O grafo K3,3 é um grafo não planar.
| Grafo bipartido completo | |
|---|---|
| Um grafo bipartido completo com m = 5 n = 3 | |
| vértices | n + m |
| arestas | mn |
| Cintura | 4 |
Um grafo G é dito ser hamiltoniano se existe um ciclo em G que contenha todos os seus vértices, sendo que cada vértice só aparece uma vez no ciclo. Este ciclo é chamado de ciclo hamiltoniano.
Um grafo simples é um grafo que não contém nem laços nem arestas múltiplas.
Podemos resumir essa definição dizendo que uma componente de um grafo não-dirigido é um subgrafo conexo maximal do grafo. (Um subgrafo conexo H de G é maximal se não existe grafo conexo H' tal que H ⊂ H' ⊆ G , ou seja, não existe subgrafo conexo H' de G tal que H é subgrafo próprio de H' .)
Definição 1– Um grafo G é dito planar se puder ser representado graficamente no plano de tal forma que não haja cruzamento de suas arestas. Caso contrário o grafo é dito não-planar. Usaremos o termo grafo plano para uma representação planar de um grafo planar.
A - conjunto de pares ordenados a = (v,w), v e w ∈ V: as arestas do grafo. Esta definição representa toda uma família de grafos. Um exemplo de elemento desta família (ver G 1) é dado por:
Em G3 há três ocorrências de laços para um grafo não orientado. Um grafo é dito ser regular quando todos os seus vértices tem o mesmo grau. O grafo G4, por exemplo, é dito ser um grafo regular-3 pois todos os seus vértices tem grau 3.
Quais os sintomas de uma lesão no ombro?
Como numerar uma planilha no LibreOffice?
Como ver se a geladeira tem gás?
O que é cateterismo em Endodontia?
Como saber se a empresa está regularizada?
Como ver a placa mãe do PC w10?
Qual a diferença entre poupança Caixa Fácil e poupança comum?
Como cuidar da minha orquídea para ela florir?
Como se cadastrar para pegar o leite do meu filho?
Quem tem direito ao cartão Merenda?
Como instalar uma impressora HP 4625?
Como saber se minha portabilidade Claro deu certo?
Como saber se a placa de vídeo é compatível com DirectX?
Como saber se o notebook suporta 64 bits?
Quais são os benefícios de treinar e desenvolver os colaboradores?