MAT1310_grafos_introducao
1 pág.

MAT1310_grafos_introducao


DisciplinaMatemática Discreta3.515 materiais76.196 seguidores
Pré-visualização1 página
MAT1310 \u2013 Matema´tica Discreta - 2012.1 PUC-Rio
Grafos - Conceitos Ba´sicos
Definic¸o\u2dces
Grafo e´ uma estrutura G(V,E), onde V e´ um conjunto finito na\u2dco vazio e os elementos de E
sa\u2dco pares de V . Os elementos de V sa\u2dco ditos ve´rtices. Os elementos de E sa\u2dco ditos arestas.
Uma aresta que liga um ve´rtice a ele mesmdo e´ dita lac¸o.
Um grafo e´ dito simples se na\u2dco tem lac¸os e nem arestas mu´ltiplas entre seus ve´rtices.
Seja G(V,E) um grafo sem lac¸os, com V = {v1, v2, . . . , vn} e E = {\u3b11, \u3b12, . . . , \u3b1m}.
Dois ve´rtices, vi e vj , sa\u2dco ditos adjacentes se {vi, vj} \u2208 E.
O nu´mero de ve´rtices adjacentes a um ve´rtice v e´ dito grau de v. Notac¸a\u2dco gr(v).
Se G e´ simples, a matriz de adjace\u2c6ncia de G e´ a matriz An×n = (aij), onde ai j = 1 se
{vi, vj} \u2208 E, e ai j = 0 caso contra´rio.
Um grafo e´ dito regular ( ou k-regular) se todos os seus ve´rtices te\u2c6m o mesmo grau (grau k).
Um grafo simples e´ dito completo se cada ve´rtice e´ adjacente a todos os os outros.
Um caminho em G e´ uma seque\u2c6ncia de ve´rtices adjacentes e o comprimento do caminho e´ o
nu´mero de arestas que ele possui.
Um caminho em G e´ dito caminho simples se passa atrave´s de seus ve´rtices uma u´nica vez.
Ciclo (ou circuito) e´ um caminho que comec¸a e acaba com o mesmo ve´rtice. Um ciclo simples
e´ um ciclo que tem um comprimento pelo menos de 3 e no qual o ve´rtice inicial so´ aparece
mais uma vez, como ve´rtice final, e os outros ve´rtices aparecem so´ uma vez.
Um grafo H(V1, E1) e´ dito subgrafo de G se V1 \u2286 V e E1 \u2286 E.
G e´ dito conexo se todo par de ve´rtices esta´ unido por um caminho. Um grafo que na\u2dco e´
conexo e´ formado por componentes conexas que sa\u2dco subgrafos conexos.
Um subgrafo H(V1, E1) de G e´ dito gerador de G se V = V1.
G e´ dito a´rvore se e´ conexo e sem ciclos.
G e´ dito floresta se na\u2dco e´ conexo, mas suas componentes conexas sa\u2dco a´rvores.
Caminho euleriano e´ um caminho que passa por todas as arestas de G uma u´nica vez. Se
existe um caminho euleriano em G que seja um ciclo, enta\u2dco G e´ dito grafo euleriano.
Caminho hamiltoniano e´ um caminho que passa atrave´s de todos os ve´rtices de G uma u´nica
vez. Se existe um caminho hamiltoniano em G que seja um ciclo, enta\u2dco G e´ dito grafo
hamiltoniano.
Um d´\u131grafo ou grafo orientado e´ um grafo G(V,E) com arestas orientadas, ou seja, as arestas
sa\u2dco pares ordenados. Nesse caso, a matriz de adjace\u2c6ncia de G e´ a matriz An×n = (aij), onde
ai j = 1 se (vi, vj) \u2208 E, e ai j = 0 caso contra´rio.
Um grafo com capacidade e´ um grafo G(V,E) e uma aplicac¸a\u2dco C : E \u2192 R+. Nesse caso, a
matriz de adjace\u2c6ncia de G e´ a matriz An×n = (aij), onde ai j = C({vi, vj}) se {vi, vj} \u2208 E, e
ai j = 0 caso contra´rio. Caso G d´\u131grafo, a matriz de adjace\u2c6ncia de G e´ a matriz An×n = (aij),
onde ai j = C(vi, vj) se (vi, vj) \u2208 E, e ai j = 0 caso contra´rio.