- Um grafo G (V, A) é definido pelo par de conjuntos V e A, onde:
- V - conjunto não vazio: os vértices ou nodos do grafo;
- A - conjunto de pares ordenados a=(v,w), v e w ∊ V: as arestas do grafo.
- Seja, por exemplo, o grafo G(V,A) dado por:
- V = {p ∣ p é uma pessoa}
- A = {(v,w) ∣ < v é amigo de w >}
- Esta definição representa toda uma família de grafos. Um exemplo de elemento desta família (ver G¹) é dado por:
- V = {Maria, Pedro, Joana, Luiz}
- A = {(Maria, Pedro), (Pedro, Maria), Joana, Maria), (Maria, Joana), (Pedro, Luiz), Luiz, Pedro), (Joana, Pedro), (Pedro, Joana)}
- Neste exemplo estamos considerando que a relação <v é amigo de w> é uma relação simétrica, ou seja, se <v é amigo de w> então <w é amigo de v>. Como consequência, as arestas que ligam os vértices não possuem qualquer orientação.
- Considere, agora, o grafo definido por:
- V = {p | p é uma pessoa da família Castro}
- A = {(v,w) | <v é pai/mãe de w>}
- Um exemplo deste grafo (ver G²) é:
- V = {Emerson, Isadora, Renata, Antônio, Cecília, Alfredo}
- A = {(Isadora, Emerson), (Antônio, Renata), (Alfredo, Emerson), (Cecília, Antônio), (Alfredo, Antônio)}
- A relação definida por A não é simétrica pois se <v é pai/mãe de w>, não é o caso de <w é pai/mãe de v>. Há, portanto, uma orientação na relação, com um correspondente efeito na representação gráfica de G.
- O grafo acima é dito ser um gráfico orientado (ou dígrafo), sendo que as conexões entre os vértices são chamados de arcos.
Ordem
- A ordem de um grafo G é dada pela cardinalidade do conjunto de vértices, ou seja, pelo número de vértices de G. Nos exemplos acima:
- ordem (G¹) = 4
- ordem (G²) = 6
- Em um grafo simples (a exemplo de G¹) dois vértices v e w são adjacentes (ou vizinhos) se há uma aresta a=(v,w) em G. Esta aresta é dita ser incidente a ambos, v e w. É o caso dos vértices Maria e Pedro em G¹. No caso do grafo ser dirigido (a exemplo de G²), a adjacência (vizinhança) é especializada em:
- Sucessor: um vértice w é sucessor de v se há um arco que parte de v e chega em w. Em G², por exemplo, diz-se que Emerson e Antônio são sucessores de Alfredo.
- Antecessor: um vértice v é antecessor de w se há um arco que parte de v e chega em w. Em G², por exemplo, diz-se que Alfredo e Cecília são antecessores de Antônio.
- O grau de um vértice é dado pelo número de arestas que lhe são incidentes. Em G¹, por exemplo:
- grau (Pedro) = 3
- grau (Maria) = 2
- No caso do grafo a ser dirigido (a exemplo de G²), a noção de grau é especializada em:
- Grau de emissão: o grau de emissão de vértice v correspondente ao número de arcos que partem de v. Em G², por exemplo:
- grau de emissão (Antônio) = 1
- grau de emissão (Alfredo) = 2
- grau de emissão (Renata) = 0
- Grau de recepção: o grau de recepção de um vértice v corresponde ao número de arcos que chegam a v. Em G², por exemplo:
- grau de recepção (Antônio) = 2
- grau de recepção (Alfredo) = 0
- grau de recepção (Renata) = 1
- Um vértice v é uma fonte de grau de recepção (v)=0. É o caso dos vértices Isadora, Alfredo e Cecília em G².
- Um vértice v é um sumidouro de grau de emissão (v)=0. É o caso dos vértices Renata e Emerson em G².
- Um laço é uma aresta ou arco do tipo a=(v,v), ou seja, que relaciona um vértice a ele próprio. Em G³ há três ocorrência de laços para um grafo não orientado.
Grafo Regular
- Um grafo é dito ser regular quando todos os seus vértices tem o mesmo grau.
- O grafo G⁴, por exemplo, é dito ser um grafo regular-3 pois todos os seus vértices tem grau 3.
Grafo Completo
- Um grafo é dito ser completo quando há uma aresta entre cada par de seus vértices. Estes grafos são designados por Kn, onde n é a ordem do grafo.
- Um grafo Kn possui o número máximo possível de arestas para um dados n. Ele é, também regular (n-1) pois todos os seus vértices tem grau n-1.
- Um grafo é dito ser bipartido quando seu conjunto de vértices V puder ser particionado em dois subconjuntos V¹ e V², tais que toda aresta de G une um vértice de V¹ a outro de V².
- Para exemplificar, sejam os conjuntos H={h | h é um homem} e M={m | m é uma mulher} e o grafo G(V,A) (ver o exemplo G⁵) onde:
- V = H ⋃ M
- A = {(v,w) | (v ∊ H e w ∊ M) ou (v ∈ M e w ∊ H) e <v foi namorado de w>}
- O grafo G⁶ é uma K³³, ou seja, um grafo bipartido completo que contém duas partições de três vértices cada. Ele é completo pois todos os vértices de uma partição estão ligados a todos os vértices da outra partição.
- Um grafo G(V,A) é dito rotulado em vértices (ou arestas) quando a cada vértice (ou aresta) estiver associado um rótulo. G⁵ é um exemplo de grafo rotulado.
- Um grafo G(V,A) é dito ser valorado quando existe uma ou mais funções relacionando V e/ou A com um conjunto de números.
- Para exemplificar (ver o grafo G⁷), seja G(V,A) onde:
- V = {v | v é uma cidade com aeroporto}
- A = {(v,w,t) | <há linha aérea ligando v a w, sendo t o tempo esperado de voo>}
Multigrafo
- Um grafo G(V,A) é dito ser um multigrafo quando existem múltiplas arestas entre pares de vértices de G. No grafo G⁸, por exemplo, há duas arestas entre os vértices A e C e entre os vértices A e B, caracterizando-o como um multigrafo.
- Um grafo Gs(Vs,As) é dito ser subgrafo de um grafo (V,A) quando Vs ⊆ V e As ⊆ A. O grafo G⁹, por exemplo, é subgrafo de G⁸.
Hipergrafo
- Um hipergrafo H(V,A) é definido pelo par de conjuntos V e A, onde:
- V - conjunto não vazio;
A - uma família e partes não vazias de V.
- Seja, por exemplo, o grafo H(V,A) dado por:
- V = {x¹, x², x³, x⁴}
- A = {{x¹, x², x⁴}, {x², x³, x⁴}, {x², x³}
Cadeia
- Uma cadeia é uma sequência qualquer de arestas adjacentes que ligam dois vértices. O conceito de cadeia vale também para grafos orientados, bastando que se ignore o sentido da orientação dos arcos. A sequência de vértices (x⁶, x⁵, x⁴, x¹) é um exemplo de cadeia em G¹¹.
- Uma cadeia é dita ser elementar se não passa duas vezes pelo mesmo vértice.
- É dita ser simples se não passa duas vezes pela mesma aresta (arco).
- O comprimento de uma cadeia é o número de aresta (arcos) que a compõe.
- Um caminho é uma cadeia na qual todos os arcos possuem a mesma orientação. Aplica-se, portanto, somente a grafos orientados. Aplica-se, portanto, somente a grafos orientados. A sequência de vértices (x¹, x², x⁵, x⁶, x³) é um exemplo de caminho em G¹¹.
- Um ciclo é uma cadeia simples e fechada (o vértice inicial é o mesmo que o vértice final). A sequência de vértices (x¹, x², x³, x⁶, x⁵, x⁴, x¹) é um exemplo de ciclo elementar em G¹¹.
- Um circuito é um caminho simples e fechado. A sequência de vértices (x¹, x², x⁵, x⁴, x¹) é um exemplo de circuito elementar em G¹¹.
- O fecho transitivo direto (ftd) de um vértice v é o conjunto de todos os vértices que podem ser atingidos por algum caminho iniciando em v. O ftd do vértice x⁵ do grafo G¹⁷, por exemplo, é o conjunto: {x¹, x², x³, x⁴, x⁵, x⁶}. Note que o próprio vértice faz parte do ftd já que ele é alcançável partindo-se dele mesmo.
- O fecho transitivo inverso (fti) de um vértice v é o conjunto de todos os vértices a partir dos quais se pode atingir v por algum caminho. O fti do vértice x⁵ do grafo G¹⁷, por exemplo, é o conjunto: {x¹, x², x⁴, x⁵, x⁷}. Note que o próprio vértice faz parte do fti já que dele se pode alcançar ele mesmo.
- Um grafo G(V,A) é dito ser conexo se há pelo menos uma cadeia ligando cada par de vértices de grafo G.
Grafo Desconexo
- Um grafo G(V,A) é dito ser desconexo se há pelo menos um par de vértices que não está ligado por nenhuma cadeia.
Componente Conexa
- Um grafo G(V,A) desconexo é formado por pelo menos dois subgrafos conexos, disjuntos em relação aos vértices e maximais em relação à inclusão. Cada um destes subgrafos conexos é disto ser uma componente conexa de G.
Grafo Fortemente Conexo
- No caso de grafos orientados, um grafo é dito ser fortemente conexo (f-conexo) se todo par de vértices está ligado por pelo menos um caminho em cada sentido, ou seja, se cada par de vértices participa de um circuito. Isto significa que cada vértice pode ser alcançável partindo-se qualquer outro vértice do grafo.
Componente Fortemente Conexa
- Um grafo G(V,A) que não é fortemente conexo é formado por pelo menos dois subgrafos fortemente conexos, disjuntos em relação aos vértices e maximais em relação à inclusão. Cada um destes subgrafos é disto ser uma componente fortemente conexa de G, a exemplo dos subgrafos identificados por S¹, S² e S³ em G¹⁷.
Vértice de Corte
- Um vértice é dito ser um vértice de corte se sua remoção (juntamente com as arestas a ele conectadas) provoca uma redução na conexidade do grafo. Os vértices x² em G¹³ e G¹⁴ são exemplos de vértices de corte.
- Uma aresta é dita ser uma ponte se sua remoção provoca uma redução na conexidade do grafo. As arestas (x¹,x²) em G¹³ e G¹⁴ são exemplos de pontes.
Nenhum comentário:
Postar um comentário