AV1 TEORIA EM GRAFOS - JULIO TADEU - UNICARIOCA - 2020.2

Prévia do material em texto

NOME COMPLETO: 
MATRÍCULA: DISCIPLINA: Teoria em Grafos TURMA: 
São 7 ciclos simples existentes no grafo, sendo eles:
A-B-C-D-E-A
A-B-F-D-E-A
B-C-D-E-A-F-B
A-B-C-D-F-A
A-F-B-A
A-F-D-E-A
B-C-D-F-B
(r * n)/2 = m
(5 * n)/2 = 90
5n = 90 * 2
5n = 180
n = 180/5
n = 36
O grafo possui 36 vértices.
 
Pode-se distribuir os 25 vértices pelas duas partições e calcular a quantidade de arestas conforme acima. Logo, o número máximo de arestas é 156. 
780 = n(n-1) Δ = - ( -1) * (-4) * 1 * (-1560) 
 2 Δ = 1 + 6240 = 6241
n² - n = 780 * 2 
n² - n = 1560 b = - ( -1) ± √6241 
n² - n – 1560 = 0 b = 1 + 79/2 = 80/2 = 40.
Possui 40 vértices.
 
Grafo planar: