Baixe o app para aproveitar ainda mais
Prévia do material em texto
2 Conceitos Básicos � Em grafos ocorrem dois tipos de elementos: � Vértices ou nós; � Arestas ou arcos. G1(V1, E1) 3 Conceitos Básicos � Grafo é um coleção de vértices e arestas. � Vértice é um objeto simples que pode ter nomes e outros atributos. � Aresta é uma conexão entre dois vértices. G2(V2, E2) 4 Representação � Um conjunto V é o conjunto de vértices de um grafo. � V2 = {v1, v2, v3, v4} � Um conjunto E é o conjunto de arestas de um grafo. � E2 = {e1, e2, e3, e4, e5} � E2 = {(v1, v3), (v3, v1), (v1, v2), (v2, v1), (v2, v4), (v4, v2), (v1, v4), (v4, v1), (v3, v4), (v4, v3)} 5 Ordem de um Grafo � O número de vértices de um grafo é dado por |V|, onde V é o conjunto de vértices de um grafo. � O número de arestas de um grafo é dado por |E|, onde E é o conjunto de arestas de um grafo. � A ordem de um grafo G é dada pela cardinalidade do conjunto de vértices, ou seja, pelo número de vértices de G (|V|). � Ordem(G1) = |V1| = 6 � Ordem(G2) = |V2| = 4 6 Conceitos Básicos � Um grafo não-direcionado G é um par (V, E), onde: � V é o conjunto de vértices e V ≠ ∅; � E consiste no par de vértices não direcionado, isto é, (vi, vj) e (vj, vi) são a mesma aresta. 7 Conceitos Básicos � Grafo direcionado ou digrafo G é um par (V, E), onde V é o conjunto finito de vértices e V ≠ ∅ e E é uma relação binária em V, ou seja, as arestas (vi, vj) ≠ (vj, vi). � Arestas têm uma direção associada. 8 Conceitos Básicos � Se (u, v) é uma aresta em um grafo direcionado G = (V, E), dize-se que (u, v) é incidente do ou sai do vértice u e é incidente no ou entra no vértice v. � Saem do vértice 2 � (2, 2), (2, 4) e (2, 5) � Entram no vértice 2 � (1, 2) e (2, 2) 9 Conceitos Básicos � Se (u, v) é uma aresta em um grafo não direcionado G = (V, E), dize-se que (u, v) é incidente nos vértices u e v. � Incidem no vértice 2 � (1, 2) e (2, 5) 10 Conceitos Básicos � Em grafos não direcionados, dois vértices são ditos adjacentes se eles são pontos finais de uma mesma aresta. � V1 e V2 são adjacentes, pois são pontos finais da aresta e2 � V2 e V3 não são adjacentes, pois não são pontos finais de nenhuma aresta 11 Conceitos Básicos � Em um grafo direcionado, um vértice v é adjacente a um vértice u se o par (u, v) é um arco, ou seja, se existe um arco que sai de u e entra em v. � O vértice 4 é adjacente ao vértice 2 e ao vértice 5, mas não é adjacente aos vértices 1, 3 e 6. 12 Conceitos Básicos � Loop ou laço: � Uma aresta associada a um par de vértices (vi, vi). � Somente em grafos direcionados. � Arestas paralelas: � Quando mais de uma aresta está associada ao mesmo par de vértices. 13 Conceitos Básicos � Duas arestas não paralelas são adjacentes se elas são incidentes a um vértice comum. As arestas (v1, v2) e (v2, v5) são adjacentes, pois incidem ao vértice v2 comum a ambas. As arestas destacadas não são adjacentes, pois são paralelas. 14 Conceitos Básicos � Grafo simples: � Um grafo que não possui loops e nem arestas paralelas. Não é um grafo simples Não é um grafo simples É um grafo simples 15 Conceitos Básicos � Um grafo ponderado é um grafo no qual existe um número associado a cada aresta. � O número associado a uma aresta é chamado peso. 16 Conceitos Básicos � Um grafo G(V, E) é dito ser rotulado em vértices ou arestas quando a cada vértice ou aresta estiver associado um rótulo. 17 Grau de um Vértice � Grau de um vértice v, representado por grau(v), em um grafo não direcionado é o número de arestas que incidem em v. � De acordo com o grau, os vértices se classificam em: � Vértice par – grau par; � Vértice ímpar – grau ímpar; � Vértice isolado – grau zero. � Sequência de graus de um grafo consiste em escrever em ordem crescente os graus dos seus vértices. 18 Grau de um Vértice v6 é um vértice isolado: grau(v6) = 0 v2 é um vértice par: grau(v6) = 4 v3 é um vértice ímpar: grau(v3) = 4 Sequência de graus: 0, 1, 2, 2, 3, 4 19 Grau de um Vértice � Em um grafo direcionado, o grau de saída de um vértice é o número de arestas que saem dele. � O grau de entrada é o número de arestas que entram nele. � O grau de um vértice em um grafo direcionado é o seu grau de entrada somado ao seu grau de saída. 20 Grau de um Vértice Grau de entrada do vértice 5: 2 Grau de saída do vértice 5: 1 Grau do vértice 5: 3 21 Grau de um Vértice � TEOREMA 1. A soma dos graus de todos os vértices de um grafo G é duas vezes o número de arestas de G. � TEOREMA 2. O número de vértices de grau ímpar em um grafo é par. ∑ = = || 1 ||2)(V i Evgrau i ∑∑ ∑ += = ímparkparj vgrau k V i vgrau ji vgrauvgrauvgrau )( || 1 )( )()()( 22 Grau de um Vértice Número de vértices de grau ímpar = 2 (v3 e v5) 6212012342)(6 1 ×==+++++=∑ =i i vgrau 23 Definições � Um grafo no qual todos os vértices possuem o mesmo grau é chamado de grafo regular. � Um vértice com nenhuma aresta incidente é chamado de vértice isolado. � Um vértice de grau 1 é chamado de vértice pendente ou terminal. Grafo Regular Vértice 4 é um vértice isolado. Os vértices 3 e 6 são vértices pendentes. 24 Definições � Um grafo sem nenhuma aresta é chamado de grafo nulo. � Todos os vértices em um grafo nulo são vértices isolados. � Um vértice v é uma fonte se o grau de entrada de v é igual a zero. � Um vértice v é um sumidouro se o grau de saída de v é igual a zero. 25 Definições � Um grafo completo é um grafo simples em que todo vértice é adjacente a todos os outros vértices. � O grafo completo de |V| vértices é freqüentemente denotado por Kn, onde n = |V|. � O número de arestas de um grafo Kn é dado por: 2 )1|(||| )!2|(|!2 |!| 2 || − = − = VV V VVC 26 Grafos Completos 27 Definições � Um grafo G = (V, E) é dito ser bipartido quando seu conjunto de vértices V puder ser particionado em dois subconjuntos V1 e V2 tais que toda aresta de G une um vértice de V1 a outro de V2. V1 V2 28 Definições � Grafo conexo: existe pelo menos um caminho entre todos os pares de vértices de G. � Um grafo desconexo consiste de 2 ou mais grafos conexos. Cada um dos subgrafos conexos é chamado de componente.
Compartilhar