Matemática | Tecnologias da Informação 2022/2023

Teoria de Grafos
GLOSSÁRIO
Grafo - um grafo é um par ordenado (V,A) em que V representa um Comprimento de um caminho: é o número de arestas que o
conjunto de vértices e A um conjunto de arestas. O conjunto de compõem, contando-se arestas múltiplas, múltiplas vezes. O
vértice, V={v1,v2,…,vn}, é finito e não vazio. comprimento de um lacete é 1.
Grafo orientado (digrafo) - é um grafo, cujas arestas são pares Caminho simples: caminho onde nenhum vértice se repete.
ordenados de elementos de V, A={ (a,b): a,bV}. Caminhos independentes: caminhos que não têm vértices em
Grafo não orientado - é um grafo, cujas arestas são pares de comum exceto, eventualmente, o primeiro e o último vértice.
elementos de V, A={ {a,b}: a,bV}. Caminho euleriano: um caminho que atravessa todas as arestas do
Grafo simples: é um grafo que não tem laços (ou lacetes) e se existe grafo uma única vez.
no máximo uma aresta entre quaisquer dois vértices. Caminho hamiltoniano: um caminho que contém todos os vértices
Grafo conexo: é um grafo em que qualquer par de vértices está do grafo e nenhum se repete.
ligado por um caminho/percurso. Ciclo: um caminho que começa e acaba no mesmo vértice. Ciclos de
Grafo desconexo: um grafo em que existe pelo menos um vértice comprimento 1 são laços.
que não se liga, por um caminho, a outro dos vértices do grafo. Ciclo simples: ciclo de comprimento superior a 2 onde nenhum
Grafo completo (𝑘𝑛 ): um grafo simples em que qualquer par de vértice se repete, à exceção do vértice inicial (que se repete como
vértices está ligado por uma aresta. vértice final).
Grafo planar: é aquele que se pode representar num plano sem que Ciclo euleriano: um ciclo que atravessa todas as arestas do grafo
qualquer aresta que se cruze. uma única vez.
Grafo bipartido: grafo cujos vértices podem ser distribuídos em dois Ciclo hamiltoniano: um ciclo que contém todos os vértices do grafo
conjuntos disjuntos, nos quais não há arestas entre vértices de um e nenhum se repete.
mesmo conjunto (não há vizinhos). Grafo acíclico: grafo sem ciclos simples.
Grafo euleriano: grafo que possui um ciclo euleriano. Contorno de um grafo: é o comprimento do ciclo simples mais curto
Grafo hamiltoniano: grafo que possui um ciclo hamiltoniano. no grafo. O contorno de um grafo acíclico é por definição infinito.
Aresta incidente a dois vértices: aresta que liga dois vértices. Subgrafo de um grafo G=(V,A): é um grafo cujo conjunto de vértices
Arestas múltiplas ou paralelas: são arestas distintas que ligam os é um subconjunto de V e cujo conjunto de arestas é um subconjunto
mesmos dois vértices. de A.

Laço (lacete ou loop): aresta com terminações no mesmo vértice. Grafo Parcial: é um subgrafo de G com o mesmo conjunto de
vértices de G.
Vértice adjacente a um dado vértice: é o vértice que está no extremo
de uma aresta que saí do vértice dado. Clique: subgrafo que é completo.

Vizinho de um vértice: é o vértice que lhe é adjacente. Matriz de Adjacência de um grafo: a matriz 𝑀 = [𝑚𝑖𝑗 ] em que o
𝑛×𝑛

Grau (valência) de um vértice: elemento 𝑚𝑖𝑗 é o número de…

a) em grafo não-orientado: número de arestas incidentes a esse a) Grafo não orientado: …arestas entre os vértices 𝑣𝑖 e 𝑣𝑗
vértice, que, no caso dos lacetes conta duas vezes. b) Grafo orientado: … arestas que saem de 𝑣𝑖 para 𝑣𝑗
b) em grafo orientado: é a soma do grau de saída e do grau de Lista de Adjacência: lista com duas colunas - a primeira com os
entrada do vértice. vértices do grafo e a segunda com os vértices adjacentes/vizinhos.
Dimensão de um grafo: número de arestas do grafo. Árvore: Grafo conexo e acíclico.
Vértice de articulação: é um vértice cuja remoção torna o grafo Floresta: Grafo desconexo e acíclico
desconexo. Árvore Geradora de G: um subgrafo de G que contém todos os
Ponte: é uma aresta cuja remoção torna o grafo desconexo. vértices de G (grafo parcial) e que é conexo e acíclico (árvore)
Conectividade de um Grafo conexo: é o menor número de vértices DFS: pesquisa em profundidade; Depth-First Search na terminologia
que é necessário remover para tornar o grafo desconexo. inglesa.
Grafo k-conexo: um grafo conexo que continua a ser conexo mesmo BFS: pesquisa em largura; Breadth-First Search na terminologia
após remover quaisquer k−1 vértices. inglesa.
Caminho (trajeto): sequência de vértices tal que em cada um dos
vértices existe uma aresta para o vértice seguinte.