-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathpg_grafo_euleriano.py
130 lines (102 loc) · 3.65 KB
/
pg_grafo_euleriano.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
import math
from networkx.generators.classic import empty_graph, path_graph, complete_graph
#DEFINICAO DAS FUNCOES
def func_graph_conected (Grafo):
#verifica se grafo é regular
fl_graph_conected = True
for node in Grafo:
if (Grafo.degree(node)<1) and (fl_graph_conected):
fl_graph_conected = False
# precisa ou não analisar se para ser conectado o grau dos vertices?
# no caso de 2 triangulos ligados por uma ponte.
return fl_graph_conected
def func_graph_regular (Grafo):
#verifica se grafo é regular
fl_graph_regular = True
first_degree = Grafo.degree(1)
for node in Grafo:
if (first_degree != Grafo.degree(node)):
fl_graph_regular = False
return fl_graph_regular
def func_cycle_euler (Grafo):
#verifica se todos os vértices têm grau par e sao conectados
fl_even_edge = True
fl_graph_conected = True
for node in Grafo:
if (Grafo.degree(node) % 2 != 0):
fl_even_edge = False
if (Grafo.degree(node)<1) and (fl_graph_conected):
fl_graph_conected = False
if (fl_even_edge and fl_graph_conected):
fl_cycle_euler = True
else:
fl_cycle_euler = False
return fl_cycle_euler
def func_graph_euler (Grafo):
#verifica se todos os vértices têm grau par
fl_graph_euler = True
for node in Grafo:
if (Grafo.degree(node) % 2 != 0):
fl_graph_euler = False
return fl_graph_euler
def func_graph_semi_euler (Grafo):
#verifica se tem dois vértices ímpares
qtd_edge_grau_impar = 0
for node in Grafo:
if (Grafo.degree(node) % 2 != 0):
qtd_edge_grau_impar+=1
if (qtd_edge_grau_impar != 2):
return False
else:
return True
# def func_bridge_euler(Grafo, v_orig):
# return
# def func_path_euler(Grafo, v_orig):
# return
# ----------------------------------------------------------------------------------
# INICIO DO PROGRAMA
G=nx.Graph()
G.add_node(1)
# G.add_nodes_from([2, 3, 4, 5, 6,7,8,9,10])
#Regular
# G.add_nodes_from([2, 3, 4, 5, 6, 7, 8])
# G.add_edges_from([(1, 2), (1,5), (1,4), (2,3), (3,4), (4,8), (8,5), (8,7), (6,2), (3,7), (6,7), (6,5)])
#Regular-Fleury
# G.add_nodes_from([2, 3, 4, 5, 6, 7, 8])
# G.add_edges_from([(1,2),(1,3),(1,6),(1,8),(2,5),(2,7),(2,4),(3,8),(4,7),(5,7),(7,8),(8,6)])
#Euleriano
G.add_edges_from([(1, 2), (1,3), (2,4), (10,6), (6,8), (3,7), (10,7), (4,5), (5,9), (8,10), (9,10)])
#Semi Euleriano
# G.add_edges_from([(1, 2), (1,3), (2,4), (10,6), (6,8), (3,7), (5,7), (4,5), (8,9), (8,10), (9,4)])
#Não Euleriano
# G.add_edges_from([(1, 2), (1,3), (2,4), (10,6), (6,8), (3,7), (5,7), (4,5), (8,9), (8,10), (9,4), (3,4),(2,9)])
print("\n"+"=========================")
if (func_graph_conected(G)):
print("\n"+"O Grafo é Conectado")
else:
print("\n"+"O Grafo não é Conectado")
if (func_graph_regular(G)):
print("\n"+"O Grafo é Regurar")
else:
print("\n"+"O Grafo não é Regular")
if func_cycle_euler(G):
print("\n"+"O Grafo tem Ciclo Euleriano")
else:
print("\n"+"O Grafo não tem Ciclo Euleriano")
if func_graph_euler(G):
print("\n"+"O Grafo é Euleriano porque só tem vértices com grau par")
# print(func_path_euler(G))
elif func_graph_semi_euler(G):
print("\n"+"O Grafo é Semi Euleriano")
# print(func_path_euler(G))
else:
print("\n"+"O Grafo não é Euleriano porque há mais de dois vértices com grau ímpar")
#plota o gráfico do grafo
figx = 15
figy = 10
fig, ax = plt.subplots(figsize=(figx, figy))
nx.draw_networkx(G,alpha=0.6,node_size=180,font_size=15)
plt.show()