Lekcja – Stopień grafu
V = {
'P' : ['D1', 'D2', 'K', 'Q', 'H'],
'D1': ['D2', 'P'],
'D2': ['D1', 'P'],
'K' : ['P', 'Q', 'H'],
'Q' : ['P', 'K', 'H'],
'H' : ['P', 'K', 'Q']
}
def node_degree(V, node):
if node in V.keys():
return len(V[node])
else:
return -1
def graph_degree(V):
max_degree = 0
for n in V.keys():
degree = node_degree(V, n)
if degree > max_degree:
max_degree = degree
return max_degree
def graph_degree2(V):
return max( [ node_degree(V, n) for n in V.keys() ] )
print(f'Degree of P: {node_degree(V, "P")}')
for n in V.keys():
print(f'Degree of {n}: {node_degree(V, n)}')
print(f'Graph degree: {graph_degree(V)}')
print(f'Graph degree: {graph_degree2(V)}')
Lab
metro = {
'Staromestska' : ['Mustek'],
'Mustek' : ['Staromestska', 'Namesti Republiky', 'Muzeum', 'Narodni trida'],
'Muzeum' : [ 'Mustek', 'Hlavni nadrazi'],
'Narodni trida' : ['Mustek'],
'Namesti Republiky' : ['Mustek', 'Florenc'],
'Florenc': ['Namesti Republiky', 'Hlavni Nadrazi'],
'Hlavni nadrazi' : ['Florenc', 'Muzeum']
}
max_degree = 0
for station, neighbours in metro.items():
if len(neighbours) > max_degree:
max_degree = len(neighbours)
print('Max degree of the graph is:', max_degree)
print('Stations with degree =', max_degree)
for station, neighbours in metro.items():
if len(neighbours) == max_degree:
print(station)