Exercício - Teoria dos Grafos - UNIP - Grafos

Prévia do material em texto

UNIP – Universidade Paulista – Alphaville
Aluno: Lucca P T	
Curso: Ciência da Computação – 4º Semestre
RA: 
Exercício Teoria dos grafos:
Peso 3,0 na prova P1
Prazo entrega: 27/03/2020
Identifique as características solicitadas dos grafos apresentados.
Exemplo
G 1
	Caracteristicas grafo G1
	 
	 
	 
	 
	 
	Ordem do grafo
	5
	 
	 
	 
	 
	Quantidade de laços
	0
	 
	 
	 
	 
	grafo Acíclico (sim/não)
	não
	ciclo (b,c,d)
	 
	 
	 
	Grafo simples (sim/Não)
	sim
	 
	 
	 
	 
	Grafo completo (sim/Não)
	não
	 
	 
	 
	 
	Grafo bipartido (sim/Não)
	não
	 
	 
	 
	 
	Grafo Bipartido completo (sim/Não)
	não
	 
	 
	 
	 
	Grafo conexo (sim/Não)
	sim
	 
	 
	 
	 
	Ggrafo Árvore (sim/Não)
	não
	 
	 
	 
	 
	Quantidade de vertices |V | ou n
	5
	 
	 
	 
	 
	Quantidade de arestas |A| ou m
	5
	 
	 
	 
	 
	Grau dos vertices d(v)
	d(a)= 1
	d(b)=3
	d(c) = 2
	d(d) =3
	d(e) =1
	Vizinhança aberta de cada vertice N(v)
	N(a)= {b}
	N(b)= {a,c,d}
	N(c)= {b,d}
	N(d)= {b,c,e}
	N(e)= {d}
	Vizinhança fechada de cada vertice N[v]
	N[a]={a,b}
	N[b]={a,b,c,d}
	N[c]={b,c,d}
	N[d]={b,c,d,e}
	N[e]={d,e}
	Grau mínimo do grafo δ(G1)
	1
	 
	 
	 
	 
	Grau maximo do grafo ∆(G1)
	3
	 
	 
	 
	 
	Soma dos graus = 2m
	10
	 
	 
	 
	 
	Grafo nulo ou vasio (sim/Não)
	não
	 
	 
	 
	 
	Grafo com grau regular (sim/não)
	não
	 
	 
	 
	 
	vertices V{}
	V = { a,b,c,d,e,}
	 
	 
	 
	 
	Arestas A{}
	A = { (a;b),(b;c), (b;d), (c;d), (d;e)} 
	 
	 
	 
	 
Reproduzir a tabela acima para os demais grafos:
G 2
	Caracteristicas grafo G2
	 
	 
	 
	 
	 
	
	
	
	
	
	
	Ordem do grafo
	6
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de laços
	0
	 
	 
	 
	 
	
	
	
	
	
	
	grafo Acíclico (sim/não)
	sim
	
	 
	 
	 
	
	
	
	
	
	
	Grafo simples (sim/Não)
	sim
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo completo (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo bipartido (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo Bipartido completo (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo conexo (sim/Não)
	sim
	 
	 
	 
	 
	
	
	
	
	
	
	Ggrafo Árvore (sim/Não)
	sim
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de vertices |V | ou n
	6
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de arestas |A| ou m
	5
	 
	 
	 
	 
	
	
	
	
	
	
	Grau dos vertices d(v)
	d(1)= 1
	d(2)= 1
	d(3) = 1
	d(4) = 4
	d(5) = 2
	d(6) = 1
	
	
	
	
	
	Vizinhança aberta de cada vertice N(v)
	N(1)= {4}
	N(2)= {4}
	N(3)= {4}
	N(4)= {1,2,3,5}
	N(5)= {4,6}
	N(6)={5}
	
	
	
	
	
	Vizinhança fechada de cada vertice N[v]
	N[1]={1,4}
	N[2]={2,4}
	N[3]={3,4}
	N[4]={1,2,3,4,5}
	N[5]={4,5,6}
	N[6]={5,6}
	
	
	
	
	
	Grau mínimo do grafo δ(G2)
	1
	 
	 
	 
	 
	
	
	
	
	
	
	Grau maximo do grafo ∆(G2)
	4
	 
	 
	 
	 
	
	
	
	
	
	
	Soma dos graus = 2m
	10
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo nulo ou vasio (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo com grau regular (sim/não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	vertices V{}
	V = {1,2,3,4,5,6}
	 
	 
	 
	 
	
	
	
	
	
	
	Arestas A{}
	A = { (1;4),(2;4), (3;4), (4;5), (5;6) } 
	 
	 
	 
	 
	
	
	
	
	
	
G 3
	Caracteristicas grafo G3
	 
	 
	 
	 
	 
	
	
	
	
	
	
	Ordem do grafo
	6
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de laços
	0
	 
	 
	 
	 
	
	
	
	
	
	
	grafo Acíclico (sim/não)
	não
	Ciclo: (a,b,f), (b,c,f), (c,e,f)
	 
	 
	 
	
	
	
	
	
	
	Grafo simples (sim/Não)
	sim
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo completo (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo bipartido (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo Bipartido completo (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo conexo (sim/Não)
	sim
	 
	 
	 
	 
	
	
	
	
	
	
	Ggrafo Árvore (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de vertices |V | ou n
	6
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de arestas |A| ou m
	8
	 
	 
	 
	 
	
	
	
	
	
	
	Grau dos vertices d(v)
	d(a)= 2
	d(b)= 3
	d(c) = 3
	d(d) = 1
	d(e) = 3
	d(f) = 4
	
	
	
	
	
	Vizinhança aberta de cada vertice N(v)
	N(a)= {b, f}
	N(b)= {a, c}
	N(c)= {b, e, f}
	N(d)= {e}
	N(e)= {c, d, f}
	N(f)={a, b, c, e}
	
	
	
	
	
	Vizinhança fechada de cada vertice N[v]
	N[a]={a, b, f}
	N[b]={a, b, c}
	N[c]={b, c, e, f}
	N[d]={d, e}
	N[e]={ c, d, e, f}
	N[f]={a, b, c, e, f}
	
	
	
	
	
	Grau mínimo do grafo δ(G3)
	1
	 
	 
	 
	 
	
	
	
	
	
	
	Grau maximo do grafo ∆(G3)
	4
	 
	 
	 
	 
	
	
	
	
	
	
	Soma dos graus = 2m
	16
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo nulo ou vasio (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo com grau regular (sim/não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	vertices V{}
	V = {a, b, c, d, e, f}
	 
	 
	 
	 
	
	
	
	
	
	
	Arestas A{}
	A = { (a;b), (b;c), (c;e), (e;d), (e;f), (f;a), (f;c), (f;b) } 
	 
	 
	 
	 
	
	
	
	
	
	
G 4
	Caracteristicas grafo G4
	 
	 
	 
	 
	 
	
	
	
	
	
	
	Ordem do grafo
	6
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de laços
	0
	 
	 
	 
	 
	
	
	
	
	
	
	grafo Acíclico (sim/não)
	não
	Ciclo: (0,2,3)
	 
	 
	 
	
	
	
	
	
	
	Grafo simples (sim/Não)
	sim
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo completo (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo bipartido (sim/Não)
	sim
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo Bipartido completo (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo conexo (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Ggrafo Árvore (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de vertices |V | ou n
	6
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de arestas |A| ou m
	5
	 
	 
	 
	 
	
	
	
	
	
	
	Grau dos vertices d(v)
	d(0)= 2
	d(1)= 1
	d(2) = 3
	d(3) = 2
	d(4) = 1
	d(5) = 1
	
	
	
	
	
	Vizinhança aberta de cada vertice N(v)
	N(0)= {2, 3}
	N(1)= {2}
	N(2)= {0,1,3}
	N(3)= {0,2}
	N(4)= {5}
	N(5)={4}
	
	
	
	
	
	Vizinhança fechada de cada vertice N[v]
	N[0]={0,2,3}
	N[1]={1,2}
	N[2]={0,1,2,3}
	N[3]={0,2,3}
	N[4]={4,5}
	N[5]={4,5}
	
	
	
	
	
	Grau mínimo do grafo δ(G4)
	1
	 
	 
	 
	 
	
	
	
	
	
	
	Grau maximo do grafo ∆(G4)
	3
	 
	 
	 
	 
	
	
	
	
	
	
	Soma dos graus = 2m
	10
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo nulo ou vasio (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo com grau regular (sim/não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	vertices V{}
	V = {0,1,2,3,4,5}
	 
	 
	 
	 
	
	
	
	
	
	
	Arestas A{}
	A = { (0;3), (3;2), (2;0), (2;1), (4;5) } 
	 
	 
	 
	 
	
	
	
	
	
	
G 5
	Caracteristicas grafo G5
	 
	 
	 
	 
	 
	
	
	
	
	
	
	Ordem do grafo
	4
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de laços
	0
	 
	 
	 
	 
	
	
	
	
	
	
	grafo Acíclico (sim/não)
	não
	Ciclo: (Maria,Pedro,Joana)
	 
	 
	 
	
	
	
	
	
	
	Grafo simples (sim/Não)
	sim
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo completo (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo bipartido (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo Bipartido completo (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo conexo (sim/Não)
	sim
	 
	 
	 
	 
	
	
	
	
	
	
	Ggrafo Árvore (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de vertices |V | ou n
	4
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de arestas |A| ou m
	4
	 
	 
	 
	 
	
	
	
	
	
	
	Grau dos vertices d(v)
	d(Maria)= 2
	d(Joana)= 2
	d(Pedro) = 3
	d(Luiz) = 1
	
	
	
	
	
	
	
	Vizinhança aberta de cada vertice N(v)
	N(Maria)= {Joana, Pedro}
	N(Joana)= {Maria, Pedro}
	N(Pedro)= {Maria, Joana, Luiz}
	N(Luiz)= {Pedro}
	
	
	
	
	
	
	
	Vizinhança fechada de cada vertice N[v]
	N[Maria]={Maria, Joana, Pedro}
	N[Joana]={Maria, Joana, Pedro}
	N[Pedro]={Maria, Joana, Pedro, Luiz}
	N[Luiz]={Pedro, Luiz}
	
	
	
	
	
	
	
	Grau mínimo do grafo δ(G5)
	1
	 
	 
	 
	 
	
	
	
	
	
	
	Grau maximo do grafo ∆(G5)
	3
	 
	 
	 
	 
	
	
	
	
	
	
	Soma dos graus = 2m
	8
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo nulo ou vasio (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo com grau regular (sim/não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	vertices V{}
	V = {Maria, Joana, Pedro, Luiz}
	 
	 
	 
	 
	
	
	
	
	
	
	Arestas A{}
	A = { (Maria;Joana), (Joana;Pedro), (Pedro;Maria), (Pedro;Luiz) } 
	 
	 
	 
	 
	
	
	
	
	
	
G 6
	Caracteristicas grafo G6
	 
	 
	 
	 
	 
	
	
	
	
	
	
	Ordem do grafo
	4
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de laços
	0
	 
	 
	 
	 
	
	
	
	
	
	
	grafo Acíclico (sim/não)
	não
	Ciclo: (a,c,d), (b,c,d)
	 
	 
	 
	
	
	
	
	
	
	Grafo simples (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo completo (sim/Não)
	sim
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo bipartido (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo Bipartido completo (sim/Não)
	nãoGrafo conexo (sim/Não)
	sim
	 
	 
	 
	 
	
	
	
	
	
	
	Ggrafo Árvore (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de vertices |V | ou n
	4
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de arestas |A| ou m
	7
	 
	 
	 
	 
	
	
	
	
	
	
	Grau dos vertices d(v)
	d(a)= 3
	d(b)= 3
	d(c) = 5
	d(d) = 3
	
	
	
	
	
	
	
	Vizinhança aberta de cada vertice N(v)
	N(a)= {c, d}
	N(b)= {c, d}
	N(c)= {a, b, d}
	N(d)= {a, b, c}
	
	
	
	
	
	
	
	Vizinhança fechada de cada vertice N[v]
	N[a]={a, c, d}
	N[b]={b, c, d}
	N[c]={a, b, c, d}
	N[d]={a, b, c, d}
	
	
	
	
	
	
	
	Grau mínimo do grafo δ(G6)
	3
	 
	 
	 
	 
	
	
	
	
	
	
	Grau maximo do grafo ∆(G6)
	5
	 
	 
	 
	 
	
	
	
	
	
	
	Soma dos graus = 2m
	14
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo nulo ou vasio (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo com grau regular (sim/não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	vertices V{}
	V = {a, b, c, d}
	 
	 
	 
	 
	
	
	
	
	
	
	Arestas A{}
	A = { (a;c), (b;c), (c;d), (d;a), (b;d) }
	 
	 
	 
	 
	
	
	
	
	
	
G 7
	Caracteristicas grafo G7
	 
	 
	 
	 
	 
	
	
	
	
	
	
	Ordem do grafo
	4
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de laços
	1
	 
	 
	 
	 
	
	
	
	
	
	
	grafo Acíclico (sim/não)
	não
	Ciclo: (V3, V2)
	 
	 
	 
	
	
	
	
	
	
	Grafo simples (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo completo (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo bipartido (sim/Não)
	sim
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo Bipartido completo (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo conexo (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Ggrafo Árvore (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de vertices |V | ou n
	4
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de arestas |A| ou m
	4
	 
	 
	 
	 
	
	
	
	
	
	
	Grau dos vertices d(v)
	d(v1)= 0
	d(v2)= 2
	d(v3) = 3
	d(v4) = 2
	
	
	
	
	
	
	
	Vizinhança aberta de cada vertice N(v)
	N(v1)= {0}
	N(v2)= {v3}
	N(v3)= {v2, v4}
	N(v4)= {v3}
	
	
	
	
	
	
	
	Vizinhança fechada de cada vertice N[v]
	N[v1]={v1}
	N[v2]={v2, v3}
	N[v3]={v2, v3, v4}
	N[v4]={v3, v4}
	
	
	
	
	
	
	
	Grau mínimo do grafo δ(G7)
	0
	 
	 
	 
	 
	
	
	
	
	
	
	Grau maximo do grafo ∆(G7)
	3
	 
	 
	 
	 
	
	
	
	
	
	
	Soma dos graus = 2m
	7
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo nulo ou vasio (sim/Não)
	Sim
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo com grau regular (sim/não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	vertices V{}
	V = {v1, v2, v3, v4}
	 
	 
	 
	 
	
	
	
	
	
	
	Arestas A{}
	A = { (v2;v3), (v3;v4) } 
	 
	 
	 
	 
	
	
	
	
	
	
G 8
	Caracteristicas grafo G8
	 
	 
	 
	 
	 
	
	
	
	
	
	
	Ordem do grafo
	5
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de laços
	0
	 
	 
	 
	 
	
	
	
	
	
	
	grafo Acíclico (sim/não)
	sim
	
	 
	 
	 
	
	
	
	
	
	
	Grafo simples (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo completo (sim/Não)
	sim
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo bipartido (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo Bipartido completo (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo conexo (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Ggrafo Árvore (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de vertices |V | ou n
	5
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de arestas |A| ou m
	0
	 
	 
	 
	 
	
	
	
	
	
	
	Grau dos vertices d(v)
	d(v1)= 0
	d(v2)= 0
	d(v3) = 0
	d(v4) = 0
	d(v5) = 0
	
	
	
	
	
	
	Vizinhança aberta de cada vertice N(v)
	N(v1)= {0}
	N(v2)= {0}
	N(v3)= {0}
	N(v4)= {0}
	N(v5)={0}
	
	
	
	
	
	
	Vizinhança fechada de cada vertice N[v]
	N[v1]={v1}
	N[v2]={v2}
	N[v3]={v3}
	N[v4]={v4}
	N[v5]={v5}
	
	
	
	
	
	
	Grau mínimo do grafo δ(G8)
	0
	 
	 
	 
	 
	
	
	
	
	
	
	Grau maximo do grafo ∆(G8)
	0
	 
	 
	 
	 
	
	
	
	
	
	
	Soma dos graus = 2m
	0
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo nulo ou vasio (sim/Não)
	Sim
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo com grau regular (sim/não)
	sim
	 
	 
	 
	 
	
	
	
	
	
	
	vertices V{}
	V = {v1, v2, v3, v4, v5}
	 
	 
	 
	 
	
	
	
	
	
	
	Arestas A{}
	A = { (0) } 
	 
	 
	 
	 
	
	
	
	
	
	
G 9
	Caracteristicas grafo G9
	 
	 
	 
	 
	 
	
	
	
	
	
	
	Ordem do grafo
	5
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de laços
	0
	 
	 
	 
	 
	
	
	
	
	
	
	grafo Acíclico (sim/não)
	sim
	
	 
	 
	 
	
	
	
	
	
	
	Grafo simples (sim/Não)
	sim
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo completo (sim/Não)
	Não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo bipartido (sim/Não)
	Sim
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo Bipartido completo (sim/Não)
	Não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo conexo (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Ggrafo Árvore (sim/Não)
	Não
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de vertices |V | ou n
	5
	 
	 
	 
	 
	
	
	
	
	
	
	Quantidade de arestas |A| ou m
	3
	 
	 
	 
	 
	
	
	
	
	
	
	Grau dos vertices d(v)
	d(Maria)= 1
	d(Joana)= 1
	d(Carla) = 1
	d(Pedro) = 2
	d(Luiz) = 1
	
	
	
	
	
	
	Vizinhança aberta de cada vertice N(v)
	N(Maria)= {Pedro}
	N(Joana)= {Luiz}
	N(Carla)= {Pedro}
	N(Pedro)= {Maria, Carla}
	N(Luiz) = {Joana}
	
	
	
	
	
	
	Vizinhança fechada de cada vertice N[v]
	N[Maria]={Maria, Pedro}
	N[Joana]={Joana, Luiz}
	N[Carla]={Carla, Pedro}
	N[Pedro]={Maria, Pedro, Carla}
	N[Luiz]={Joana, Luiz}
	
	
	
	
	
	
	Grau mínimo do grafo δ(G9)
	1
	 
	 
	 
	 
	
	
	
	
	
	
	Grau maximo do grafo ∆(G9)
	2
	 
	 
	 
	 
	
	
	
	
	
	
	Soma dos graus = 2m
	6
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo nulo ou vasio (sim/Não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	Grafo com grau regular (sim/não)
	não
	 
	 
	 
	 
	
	
	
	
	
	
	vertices V{}
	V = {Maria, Joana, Carla, Pedro, Luiz}
	 
	 
	 
	 
	
	
	
	
	
	
	Arestas A{}
	A = {(Maria;Pedro), (Joana;Luiz), (Carla;Pedro), }