grafos

Prévia do material em texto

CENTRO UNIVERSITÁRIO DA FEI
Graduação em Ciência da Computação
Gabriel Bueno Vila Real de Oliveira - RA: 22119077-0
Thiago Soares Cardoso da Silva - RA: 22119044-0
Projeto de Teoria dos Grafos
São Bernardo do Campo
2019
1 - Relatório com os itens exigidos
1.1 Arestas Paralelas
Dado um grafo G, se G conter n arestas e com extre-
midades em dois vértices adjacentes vx e vy, determi-
namos tais arestas como paralelas.
Exemplo:
G:
v1 v2
e1
e2
Analisando G, podemos concluir que as arestas e1
e e2 são paralelas, pois ambas conectam os vértices v1
e v2.
1.2 Laços
Laços, também ditos loops ou nós, são arestas que co-
nectam um vértice v a ele mesmo.
Exemplo:
H:
v1 v2 v3
e1
e2
e3
e4
e5
Analisando H, podemos concluir que e1 e e3 são
laços dos vértices v1 e v2, respectivamente.
1.3 Grafos Simples
Um grafoG é dito simples⇔ não possuir laços e arestas
paralelas.
1.4 Grau de um vértice
Denotado por grau(v), gr(v), deg(v) ou d(v), o grau de
um vértice é o número de arestas que incidem em um
vértice v ∈ V(G), sendo que os laços são contados duas
vezes.
Exemplo:
I:
v1 v2
v3 v4
Analisando I, podemos concluir que os vértices v1,
v2, v3 e v4 possuem graus 3, 4, 1 e 4, respectivamente,
pois estes são os números de arestas que incidem sobre
eles.
1.5 Relação entre arestas e graus dos
vértices
Dado um grafo G = (V, E) , temos que a soma dos
graus de todos os vértices é o dobro do número de ares-
tas.
g(v1) + g(v2) + g(v3) + · · ·+ g(vn) = 2|E(G)| (1)
∴
∑
v∈V (G)
g(v) = 2|E(G)| (2)
1.6 Grafos Completos
Um grafo G de n vértices, é dito completo se for sim-
ples e se cada vértice for adjacente a todos os outros.
Podemos denotar tal tipo de grafo por Kn.
Exemplos:
K4:
1
2
3
4
K5:
1
2
34
5
1.7 Grafos Regulares
Um grafo é dito regular quando todos os seus vértices
têm o mesmo grau.
Exemplos: Os grafos completos com 2, 3, 4, e 5
vértices são grafos regulares.
1
23
1
2
K3 e K2 são regulares.
2
1.8 Grafos Bipartidos
Um grafo G = (V,E) é dito bipartido se V(G) = x∪ y,
com x 6= ∅ 6=y e x ∩ y = ∅ tal que cada aresta e de G
tem uma extremidade em x e outra em y. Equivalente-
mente, podemos dizer que um grafo é bipartido se não
possuir qualquer ciclo de comprimento ímpar.
Exemplos:
G:
v1
v2
v3
v4
Se considerarmos G como bipartido e supormos que
v1 ∈ x, então {v2, v4} ∈ y. Absurdo, pois v2 e v4 são
adjacentes! ∴ G não é bipartido.
K3,3:
v1 v2 v3
v4v5v6
K3,3 é bipartido, com bipartição em x = {v1, v2, v3}
e y = {v4, v5, v6}
1.9 Grafos bipartidos completos
Um grafo G, é considerado bipartido completo se é sim-
ples, bipartido com bipartição (x, y), tal que cada vér-
tice de x é adjacente a todo vértice de y. Considerando
|x| = m e |y| = n, podemos denotar este tipo de grafo
por Km,n.
Exemplo:
K2,2:
x x
yy
K2,2 é bipartido completo.
3