Esta é uma lista de algumas definições da Teoria dos Grafos simples.
— publicidade —
Conjunto de vértices
É qualquer conjunto não vazio cujos elementos chamamos de vértices.
Denotarei um conjunto de vértices por $V$.
Aresta
Seja $V$ um conjunto de vértices. Uma aresta é um par não ordenado $\{u, v \}$ onde $u, v \in V$ e $u \neq v$.
Denotarei a aresta $\{u, v \}$ por $uv$ e um conjunto de arestas por $E$.
Grafo simples
Sejam $V$ um conjunto de vértices e $E$ um conjunto de arestas. Um grafo simples é o par ordernado $(V, E)$.
A partir daqui, sempre que eu escrever ‘grafo’ quero me referir a um grafo simples.
Vértices adjacentes (ou vizinhos)
Sejam $G = (V, E)$ um grafo e $u, v \in V$ vértices. $u$ e $v$ são ditos vértices adjacentes se são conectados por uma aresta. Isto é, se $\exists uv = \{u, v\} \in E$.
Vizinhança de um vértice
Denotarei a vizinhança de $v$ por $N(v)$.
Note que $N(v) \subset V$.
Corte de um vértice
Denotarei o corte de um vértice por $\nabla(v)$.
Note que $\nabla(v) \subset E$.
Grau de um vértice
Note que $d(v) = |N(v)| = |\nabla(v)|$ para todo vértice $v$, mas acho que isso não é verdade para conjuntos de vértices.
Subgrafo
Seja $G = (V(G), E(G))$ um grafo. Um subgrafo de $G$ é qualquer grafo $H$ tal que $V(H) \subset V(G)$ e $E(H) \subset E(G)$.
Caminho
Sejam $V$ um conjunto de vértices. Um caminho é qualquer grafo da forma $(\{v_1, v_2, …, v_n \}, \{v_i v_{i+1} | 1 \leq i < n \})$.
Denotarei o caminho $(\{v_1, v_2, …, v_n \}, \{v_i v_{i+1} | 1 \leq i < n \})$ simplesmente por $v_1 v_2 … v_n$.
Se um caminho $v_1 … v_n$ é subgrafo de um grafo $G$, dizemos simplesmente que $v_1 … v_n$ é um caminho em $G$.
Passeio
É um caminho com repetição.
A rigor devo definir passeio como um conjunto, mas não sei fazer isso.
Componente conexo
Ciclo
Seja $V$ um conjunto de vértices. Um ciclo é um grafo da forma $(\{v_1, v_2, …, v_n \}, \{v_i v_{i+1} | 1 \leq i < n \} \cup \{v_n v_1 \})$, com $n \geq 3$.
Em outras palavras, um ciclo é um caminho em que o primeiro e o último vértices coincidem.
Denotarei o ciclo $(\{v_1, v_2, …, v_n \}, \{v_i v_{i+1} | 1 \leq i < n \} \cup \{v_n v_1 \})$ por $v_1 v_2 … v_n v_1$.
Se um ciclo $v_1 … v_n v_1$ é subgrafo de um grafo $G$, dizemos simplesmente que $v_1 … v_n v_1$ é um ciclo em $G$.
Árvore
É um grafo conexo e sem ciclos.
É bem interessante o fato de que se adcionarmos ou removermos uma aresta em uma árvore ela deixa de ser árvore.
Grafo planar
Isomorfismo entre grafos
Se existir um isomorfismo entre dois grafos direi que eles são isomorfos.
Uma forma de entender a definição acima de isomorfismo é: dois grafos são isomorfos se é possível alterar os nomes dos vértices de um deles de tal modo que os dois grafos fiquem iguais.
Referências:
Livro “Uma Introdução Sucinta à Teoria dos Grafos”
Matemática Discreta – L. Lovász, J. Pelikán e K. Vesztergombi
— publicidade —
1 comentário em “Definições da Teoria dos Grafos simples”