https://www.udacity.com/course/viewer#!/c-cs215/l-48747095/e-48747094/m-48730167
LESSON 1
Эйлеровым путем в графе называется путь, который проходит по каждому ребру, причем ровно один раз.
В неориентированном графе
Согласно теореме, доказанной Эйлером, эйлеров цикл существует тогда и только тогда, когда граф связный и в нём отсутствуют вершины нечётной степени.
Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более двух вершин нечётной степени. Ввиду леммы о рукопожатиях, число вершин с нечётной степенью должно быть четным. А значит эйлеров путь существует только тогда, когда это число равно нулю или двум. Причём когда оно равно нулю, эйлеров путь вырождается в эйлеров цикл.
В ориентированном графе
Ориентированный граф G=(V,A) содержит эйлеров цикл тогда и только тогда, когда он сильно связан и для каждой вершины графа её полустепень захода равна её полустепени исхода, то есть в вершину входит столько же ребер, сколько из неё и выходит.
Код проверки графа на эйлеровость:
boolean checkForEulerPath():
int OddVertex = 0
for v : v \in V
if \operatorname{deg}(v) mod 2 == 1
OddVertex++
if OddVertex > 2// если количество вершин с нечетной степенью больше двух, то граф не является эйлеровым
return false
boolean visited(|V|, false) // массив инициализируется значениями false
for v : v \in V
if \operatorname{deg}(v) > 0
dfs(v, visited)
break
for v : v \in V
if \operatorname{deg}(v) > 0 and not visited[v] // если количество компонент связности, содержащие ребра, больше одной,
return false // то граф не является эйлеровым
return true // граф является эйлеровым
Код построения Эйлерова пути:
function findEulerPath(v): // если граф является полуэйлеровым, то алгоритм следует запускать из вершины нечетной степени
for u : u \in V
if \operatorname{deg}(u) mod 2 == 1
v = u
break
S.push(v) // S — стек
while not S.empty()
w = S.top()
for u : u \in V
if (w, u) \in E // нашли ребро, по которому ещё не прошли
S.push(u) // добавили новую вершину в стек
E.remove(w, u)
break
if w == S.top()
S.pop() // не нашлось инцидентных вершине w рёбер, по которым ещё не прошли
print(w)
Рекурсивная реализация
function findEulerPath(v : Vertex):
for (v,u) \in E
remove (v, u)
findEulerPath(u)
print(v)
Оператор a >> n возвращает число, которое получается из a сдвигом всех бит на n позиций вправо, при этом самые правые n бит отбрасываются. Например:
a = 43 # 0b101011
b = a >> 1 # 0b10101 == 21
c = a >> 2 # 0b1010 == 10
d = a >> 3 # 0b101 == 5
e = a >> 5 # 0b1 == 1
Понятно, что для положительных чисел битовый сдвиг числа вправо на n равносилен целочисленному делению на 2^n. Для отрицательных чисел в языке Питон операции битового сдвига неприменимы.
Аналогично, битовый сдвиг влево на n бит равносилен (для положительных чисел) умножению на 2^n и осуществляется при помощи оператора <<:
a = 5 # 0b101
b = a << 1 # 0b1010 == 10
c = a << 2 # 0b10100 == 20
d = 2 << 3 # 0b101000 == 40
import math
def time(n):
""" Return the number of steps
necessary to calculate
`print countdown(n)`"""
steps = 0
if n % 5 == 0:
steps = 2*n/5 + 3
else:
steps = 2*(n/5 + 1) + 3
# YOUR CODE HERE
return steps
print time(50)
print time(51)
def countdown(x):
y = 0
while x > 0:
x = x - 5
y = y + 1
print y
print countdown(50)
# counting steps in naive as a function of a
def naive(a, b):
x = a
y = b
z = 0
while x > 0:
z = z + y
x = x - 1
return z
def time(a):
# The number of steps it takes to execute naive(a, b)
# as a function of a
# your code here
return 2*a + 3
print time(2)
PROBLEM SET 1
#3
# Eulerian Tour Ver 1
#
# Write a function, `create_tour` that takes as
# input a list of nodes
# and outputs a list of tuples representing
# edges between nodes that have an Eulerian tour.
#
#########
def get_degree(tour):
degree = {}
for x, y in tour:
degree[x] = degree.get(x, 0) + 1
degree[y] = degree.get(y, 0) + 1
return degree
#########
def get_degree(tour):
degree = {}
for x, y in tour:
degree[x] = degree.get(x, 0) + 1
degree[y] = degree.get(y, 0) + 1
return degree
def check_edge(t, b, nodes):
"""
t: tuple representing an edge
b: origin node
nodes: set of nodes already visited
if we can get to a new node from `b` following `t`
then return that node, else return None
"""
if t[0] == b:
if t[1] not in nodes:
return t[1]
elif t[1] == b:
if t[0] not in nodes:
return t[0]
return None
def connected_nodes(tour):
"""return the set of nodes reachable from
the first node in `tour`"""
a = tour[0][0]
nodes = set([a])
explore = set([a])
while len(explore) > 0:
# see what other nodes we can reach
b = explore.pop()
for t in tour:
node = check_edge(t, b, nodes)
if node is None:
continue
nodes.add(node)
explore.add(node)
return nodes
def is_eulerian_tour(nodes, tour):
# all nodes must be even degree
# and every node must be in graph
degree = get_degree(tour)
for node in nodes:
try:
d = degree[node]
if d % 2 == 1:
print "Node %s has odd degree" % node
return False
except KeyError:
print "Node %s was not in your tour" % node
return False
connected = connected_nodes(tour)
if len(connected) == len(nodes):
return True
else:
print "Your graph wasn't connected"
return False
def test():
nodes = [20, 21, 22, 23, 24, 25]
tour = create_tour(nodes)
return is_eulerian_tour(nodes, tour)
def edge(x, y):
return (x, y) if x < y else (y, x)
def create_tour(nodes):
tour_list = []
n = len(nodes)
for i in range(n):
t = edge(nodes[i], nodes[(i+1) % n])
tour_list.append(t)
return tour_list
print create_tour([0,1,2,3,4,])
print test()
def edge(x, y):
return (x, y) if x < y else (y, x)
def create_tour(nodes):
# there are lots of ways to do this
# a boring solution could just connect
# the first node with the second node
# second with third... and the last with the
# first
tour = []
l = len(nodes)
for i in range(l):
t = edge(nodes[i], nodes[(i+1) % l])
tour.append(t)
return tour
And here is a slightly more complicated solution with some randomness:
from random import randint
def edge(x, y):
return (x, y) if x < y else (y, x)
def poprandom(nodes):
x_i = randint(0, len(nodes) - 1)
return nodes.pop(x_i)
def pickrandom(nodes):
x_i = randint(0, len(nodes) - 1)
return nodes[x_i]
def check_nodes(x, nodes, tour):
for i, n in enumerate(nodes):
t = edge(x, n)
if t not in tour:
tour.append(t)
nodes.pop(i)
return n
return None
def create_tour(nodes):
connected = []
degree = {}
unconnected = [n for n in nodes]
tour = []
# create a connected graph
# first, pick two random nodes for an edge
x = poprandom(unconnected)
y = poprandom(unconnected)
connected.append(x)
connected.append(y)
tour.append(edge(x,y))
degree[x] = 1
degree[y] = 1
# then, pick a random node from the unconnected
# list and create an edge to it
while len(unconnected) > 0:
x = pickrandom(connected)
y = poprandom(unconnected)
connected.append(y)
tour.append(edge(x, y))
degree[x] += 1
degree[y] = 1
# now make sure each node has an even degree.
# have the problem of not adding a duplicate edge
odd_nodes = [k for k, v in degree.items() if v % 2 == 1]
even_nodes = [k for k, v in degree.items() if v % 2 == 0]
# there will always be an even number of odd nodes
# (hint: the sum of degrees of a graph is even)
# so we can just connect pairs of unconnected edges
while len(odd_nodes) > 0:
x = poprandom(odd_nodes)
cn = check_nodes(x, odd_nodes, tour)
if cn is not None:
even_nodes.append(x)
even_nodes.append(cn)
else:
# if we get here
# the node is already connected to
# all the odd nodes so we need to find an
# even one to connect to
cn = check_nodes(x, even_nodes, tour)
# cn cannot be None, and needs to be
# added to the odd_nodes list
odd_nodes.append(cn)
# but, x is now an even node
even_nodes.append(x)
return tour
#4
Advantages:
- a small memory size
- convenient for the construction of algorithms
Disadvantages:
- it does not give a clear idea immediately about a number of edges in a given node
Способы представления графа в информатике
Матрица смежности
Таблица, где как столбцы, так и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу (либо наоборот).
Это наиболее удобный способ представления плотных графов.
Недостатком являются требования к памяти, прямо пропорциональные квадрату количества вершин.
Двумерный массив;
Матрица с пропусками;
Неявное задание
Матрица инцидентности
Основная статья: Матрица инцидентности
Таблица, где строки соответствуют вершинам графа, а столбцы соответствуют связям (рёбрам) графа.
В ячейку матрицы на пересечении строки i со столбцом j записывается:
1 в случае, если связь j «выходит» из вершины i,
−1, если связь «входит» в вершину,
0 во всех остальных случаях (то есть если связь является петлёй или связь не инцидентна вершине)
Данный способ является самым ёмким (размер пропорционален |V| |E|) для хранения, поэтому применяется очень редко, в особых случаях (например, для быстрого нахождения циклов в графе).
Список смежности
Список, где каждой вершине графа соответствует строка, в которой хранится список смежных вершин. Такая структура данных не является таблицей в обычном понимании, а представляет собой «список списков».
Размер занимаемой памяти: O(|V|+|E|).
Это наиболее удобный способ для представления разреженных графов, а также при реализации базовых алгоритмов обхода графа в ширину или глубину, где нужно быстро получать «соседей» текущей просматриваемой вершины.
Список рёбер
Список, где каждому ребру графа соответствует строка, в которой хранятся две вершины, инцидентные ребру.
Размер занимаемой памяти: O(|E|).
Это наиболее компактный способ представления графов, поэтому часто применяется для внешнего хранения или обмена данными.
#9
# Write a function, `count`
# that returns the units of time
# where each print statement is one unit of time
# and each evaluation of range also takes one unit of time
def count(n):
m = 2
if n != 0:
m = count(n-1)
m = m + n
# Your code here to count the units of time
# it takes to execute clique
return m
def clique(n):
print "in a clique..."
for j in range(n):
for i in range(j):
print i, "is friends with", j
print count(5)
# Write a function, `count`
# that returns the units of time
# where each print statement is one unit of time
# and each evaluation of range also takes one unit of time
def count(n):
# Your code here to count the units of time
# it takes to execute clique
return 2 + n * (n + 1) / 2
def clique(n):
print "in a clique..."
for j in range(n):
for i in range(j):
print i, "is friends with", j
#10
# Find Eulerian Tour
#
# Write a function that takes in a graph
# represented as a list of tuples
# and return a list of nodes that
# you would follow on an Eulerian Tour
#
# For example, if the input graph was
# [(1, 2), (2, 3), (3, 1)]
# A possible Eulerian tour would be [1, 2, 3, 1]
graph = [(0, 1), (1, 5), (1, 7), (4, 5), (4, 8), (1, 6), (3, 7), (5, 9), (2, 4), (0, 4), (2, 5), (3, 6), (8, 9)]
def edge(x, y):
return (x, y) if x < y else (y, x)
def get_nodes(graph):
nodes = []
for element in graph:
if element[0] not in nodes:
nodes.append(element[0])
if element[1] not in nodes:
nodes.append(element[1])
return nodes
def diff_list(l1,l2):
diff = []
for element in l1:
if element not in l2:
diff.append(element)
return diff
def create_tour(nodes):
tour_list = []
n = len(nodes)
for i in range(n):
t = edge(nodes[i], nodes[(i+1) % n])
tour_list.append(t)
return tour_list
def get_degree(tour):
degree = {}
for x, y in tour:
degree[x] = degree.get(x, 0) + 1
degree[y] = degree.get(y, 0) + 1
return degree
print get_degree(graph)
def check_edge(t, b, nodes):
"""
t: tuple representing an edge
b: origin node
nodes: set of nodes already visited
if we can get to a new node from `b` following `t`
then return that node, else return None
"""
if t[0] == b:
if t[1] not in nodes:
return t[1]
elif t[1] == b:
if t[0] not in nodes:
return t[0]
return None
def connected_nodes(tour):
"""return the set of nodes reachable from
the first node in `tour`"""
a = tour[0][0]
nodes = set([a])
explore = set([a])
while len(explore) > 0:
# see what other nodes we can reach
b = explore.pop()
for t in tour:
node = check_edge(t, b, nodes)
if node is None:
continue
nodes.add(node)
explore.add(node)
return nodes
def is_eulerian_tour(nodes, tour):
# all nodes must be even degree
# and every node must be in graph
degree = get_degree(tour)
for node in nodes:
try:
d = degree[node]
if d % 2 == 1:
print "Node %s has odd degree" % node
return False
except KeyError:
print "Node %s was not in your tour" % node
return False
connected = connected_nodes(tour)
if len(connected) == len(nodes):
return True
else:
print "Your graph wasn't connected"
return False
print is_eulerian_tour(get_nodes(graph), graph)
def get_way(graph):
node_set = get_nodes(graph)
current_node = node_set[1]
current_edge = graph[0]
visited_edges = [current_edge]
eulerian_tour = [current_edge[0], current_edge[1]]
for v in range(len(graph)/2):
for element in graph[1:]:
for i in range(2):
if i == 0: j =1
else: j = 0
if element not in visited_edges and element[i] == current_node:
eulerian_tour.append(element[j])
visited_edges.append(element)
current_node = element[j]
rest = diff_list(graph,visited_edges)
return eulerian_tour, rest
print get_way(graph)[0]
def find_eulerian_tour(graph):
nodes = get_nodes(graph)
if not is_eulerian_tour(nodes, graph):
print "Your graph has not Eulerian Tour"
return None
result = get_way(graph)[0]
rest = get_way(graph)[1]
if rest == []:
return result
current_result = get_way(rest)[0]
current_rest = get_way(rest)[0]
i = result.index(current_result[0])
result = result[:i] + current_result + result[i+1:]
return result
print find_eulerian_tour(graph)
#############################################################
def edge(x, y):
return (x, y) if x < y else (y, x)
def create_tour(nodes):
# there are lots of ways to do this
# a boring solution could just connect
# the first node with the second node
# second with third... and the last with the
# first
tour = []
l = len(nodes)
for i in range(l):
t = edge(nodes[i], nodes[(i+1) % l])
tour.append(t)
return tour
And here is a slightly more complicated solution with some randomness:
from random import randint
def edge(x, y):
return (x, y) if x < y else (y, x)
def poprandom(nodes):
x_i = randint(0, len(nodes) - 1)
return nodes.pop(x_i)
def pickrandom(nodes):
x_i = randint(0, len(nodes) - 1)
return nodes[x_i]
def check_nodes(x, nodes, tour):
for i, n in enumerate(nodes):
t = edge(x, n)
if t not in tour:
tour.append(t)
nodes.pop(i)
return n
return None
def create_tour(nodes):
connected = []
degree = {}
unconnected = [n for n in nodes]
tour = []
# create a connected graph
# first, pick two random nodes for an edge
x = poprandom(unconnected)
y = poprandom(unconnected)
connected.append(x)
connected.append(y)
tour.append(edge(x,y))
degree[x] = 1
degree[y] = 1
# then, pick a random node from the unconnected
# list and create an edge to it
while len(unconnected) > 0:
x = pickrandom(connected)
y = poprandom(unconnected)
connected.append(y)
tour.append(edge(x, y))
degree[x] += 1
degree[y] = 1
# now make sure each node has an even degree.
# have the problem of not adding a duplicate edge
odd_nodes = [k for k, v in degree.items() if v % 2 == 1]
even_nodes = [k for k, v in degree.items() if v % 2 == 0]
# there will always be an even number of odd nodes
# (hint: the sum of degrees of a graph is even)
# so we can just connect pairs of unconnected edges
while len(odd_nodes) > 0:
x = poprandom(odd_nodes)
cn = check_nodes(x, odd_nodes, tour)
if cn is not None:
even_nodes.append(x)
even_nodes.append(cn)
else:
# if we get here
# the node is already connected to
# all the odd nodes so we need to find an
# even one to connect to
cn = check_nodes(x, even_nodes, tour)
# cn cannot be None, and needs to be
# added to the odd_nodes list
odd_nodes.append(cn)
# but, x is now an even node
even_nodes.append(x)
return tour
Last login: Sat Jun 18 09:02:37 on ttys000
olgabelitskaya (master) ~ $ cd version-control
olgabelitskaya (master) version-control $ git status
On branch master
Your branch is up-to-date with 'exercises/master'.
Untracked files:
(use "git add <file>..." to include in what will be committed)
reflections-cs215/
nothing added to commit but untracked files present (use "git add" to track)
olgabelitskaya (master) version-control $ git add 'reflections-cs215/'
olgabelitskaya (master +) version-control $ git status
On branch master
Your branch is up-to-date with 'exercises/master'.
Changes to be committed:
(use "git reset HEAD <file>..." to unstage)
new file: reflections-cs215/lesson1_reflections_ob.txt
olgabelitskaya (master +) version-control $ git commit -m "Add reflections cs215"
[master 37adbd0] Add reflections cs215
1 file changed, 60 insertions(+)
create mode 100644 reflections-cs215/lesson1_reflections_ob.txt
olgabelitskaya (master) version-control $ git status
On branch master
Your branch is ahead of 'exercises/master' by 1 commit.
(use "git push" to publish your local commits)
nothing to commit, working directory clean
olgabelitskaya (master) version-control $ git push exercises master
Counting objects: 4, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (4/4), done.
Writing objects: 100% (4/4), 5.43 KiB | 0 bytes/s, done.
Total 4 (delta 1), reused 0 (delta 0)
To https://github.com/OlgaBelitskaya/my-exercises.git
56194ea..37adbd0 master -> master
olgabelitskaya (master) version-control $
Eulerian Path and Circuit. Copyright © 2004-2016 Dumitru Ciubatii.
Task:
Given an undirected or a directed graph, find a path or circuit that passes through each edge exactly once.
Solution:
First let's see the conditions for an undirected graph:
An undirected graph has an eulerian circuit if and only if it is connected and each vertex has an even degree (degree is the number of edges that are adjacent to that vertex).
An undirected graph has an eulerian path if and only if it is connected and all vertices except 2 have even degree. One of those 2 vertices that have an odd degree must be the start vertex, and the other one must be the end vertex.
For a directed graph we have:
A directed graph has an eulerian circuit if and only if it is connected and each vertex has the same in-degree as out-degree.
A directed graph has an eulerian path if and only if it is connected and each vertex except 2 have the same in-degree as out-degree, and one of those 2 vertices has out-degree with one greater than in-degree (this is the start vertex), and the other vertex has in-degree with one greater than out-degree (this is the end vertex).
Algorithm for undirected graphs:
Start with an empty stack and an empty circuit (eulerian path).
- If all vertices have even degree - choose any of them.
- If there are exactly 2 vertices having an odd degree - choose one of them.
- Otherwise no euler circuit or path exists.
If current vertex has no neighbors - add it to circuit, remove the last vertex from the stack and set it as the current one. Otherwise (in case it has neighbors) - add the vertex to the stack, take any of its neighbors, remove the edge between selected neighbor and that vertex, and set that neighbor as the current vertex.
Repeat step 2 until the current vertex has no more neighbors and the stack is empty.
Note that obtained circuit will be in reverse order - from end vertex to start vertex.
Algorithm for directed graphs:
Start with an empty stack and an empty circuit (eulerian path).
- If all vertices have same out-degrees as in-degrees - choose any of them.
- If all but 2 vertices have same out-degree as in-degree, and one of those 2 vertices has out-degree with one greater than its in-degree, and the other has in-degree with one greater than its out-degree - then choose the vertex that has its out-degree with one greater than its in-degree.
- Otherwise no euler circuit or path exists.
If current vertex has no out-going edges (i.e. neighbors) - add it to circuit, remove the last vertex from the stack and set it as the current one. Otherwise (in case it has out-going edges, i.e. neighbors) - add the vertex to the stack, take any of its neighbors, remove the edge between that vertex and selected neighbor, and set that neighbor as the current vertex.
Repeat step 2 until the current vertex has no more out-going edges (neighbors) and the stack is empty.
Note that obtained circuit will be in reverse order - from end vertex to start vertex.
Both algorithms will give you the tour in reverse order, i.e. from the end vertex to the start vertex.
As you can see - the algorithms are very similar.
Complexity:
The complexity of both algorithms is O(N+M), where N is the number of vertices and M is the number of edges.
LESSON 1
Эйлеровым путем в графе называется путь, который проходит по каждому ребру, причем ровно один раз.
В неориентированном графе
Согласно теореме, доказанной Эйлером, эйлеров цикл существует тогда и только тогда, когда граф связный и в нём отсутствуют вершины нечётной степени.
Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более двух вершин нечётной степени. Ввиду леммы о рукопожатиях, число вершин с нечётной степенью должно быть четным. А значит эйлеров путь существует только тогда, когда это число равно нулю или двум. Причём когда оно равно нулю, эйлеров путь вырождается в эйлеров цикл.
В ориентированном графе
Ориентированный граф G=(V,A) содержит эйлеров цикл тогда и только тогда, когда он сильно связан и для каждой вершины графа её полустепень захода равна её полустепени исхода, то есть в вершину входит столько же ребер, сколько из неё и выходит.
Код проверки графа на эйлеровость:
boolean checkForEulerPath():
int OddVertex = 0
for v : v \in V
if \operatorname{deg}(v) mod 2 == 1
OddVertex++
if OddVertex > 2// если количество вершин с нечетной степенью больше двух, то граф не является эйлеровым
return false
boolean visited(|V|, false) // массив инициализируется значениями false
for v : v \in V
if \operatorname{deg}(v) > 0
dfs(v, visited)
break
for v : v \in V
if \operatorname{deg}(v) > 0 and not visited[v] // если количество компонент связности, содержащие ребра, больше одной,
return false // то граф не является эйлеровым
return true // граф является эйлеровым
Код построения Эйлерова пути:
function findEulerPath(v): // если граф является полуэйлеровым, то алгоритм следует запускать из вершины нечетной степени
for u : u \in V
if \operatorname{deg}(u) mod 2 == 1
v = u
break
S.push(v) // S — стек
while not S.empty()
w = S.top()
for u : u \in V
if (w, u) \in E // нашли ребро, по которому ещё не прошли
S.push(u) // добавили новую вершину в стек
E.remove(w, u)
break
if w == S.top()
S.pop() // не нашлось инцидентных вершине w рёбер, по которым ещё не прошли
print(w)
Рекурсивная реализация
function findEulerPath(v : Vertex):
for (v,u) \in E
remove (v, u)
findEulerPath(u)
print(v)
Оператор a >> n возвращает число, которое получается из a сдвигом всех бит на n позиций вправо, при этом самые правые n бит отбрасываются. Например:
a = 43 # 0b101011
b = a >> 1 # 0b10101 == 21
c = a >> 2 # 0b1010 == 10
d = a >> 3 # 0b101 == 5
e = a >> 5 # 0b1 == 1
Понятно, что для положительных чисел битовый сдвиг числа вправо на n равносилен целочисленному делению на 2^n. Для отрицательных чисел в языке Питон операции битового сдвига неприменимы.
Аналогично, битовый сдвиг влево на n бит равносилен (для положительных чисел) умножению на 2^n и осуществляется при помощи оператора <<:
a = 5 # 0b101
b = a << 1 # 0b1010 == 10
c = a << 2 # 0b10100 == 20
d = 2 << 3 # 0b101000 == 40
import math
def time(n):
""" Return the number of steps
necessary to calculate
`print countdown(n)`"""
steps = 0
if n % 5 == 0:
steps = 2*n/5 + 3
else:
steps = 2*(n/5 + 1) + 3
# YOUR CODE HERE
return steps
print time(50)
print time(51)
def countdown(x):
y = 0
while x > 0:
x = x - 5
y = y + 1
print y
print countdown(50)
# counting steps in naive as a function of a
def naive(a, b):
x = a
y = b
z = 0
while x > 0:
z = z + y
x = x - 1
return z
def time(a):
# The number of steps it takes to execute naive(a, b)
# as a function of a
# your code here
return 2*a + 3
print time(2)
PROBLEM SET 1
#3
# Eulerian Tour Ver 1
#
# Write a function, `create_tour` that takes as
# input a list of nodes
# and outputs a list of tuples representing
# edges between nodes that have an Eulerian tour.
#
#########
def get_degree(tour):
degree = {}
for x, y in tour:
degree[x] = degree.get(x, 0) + 1
degree[y] = degree.get(y, 0) + 1
return degree
#########
def get_degree(tour):
degree = {}
for x, y in tour:
degree[x] = degree.get(x, 0) + 1
degree[y] = degree.get(y, 0) + 1
return degree
def check_edge(t, b, nodes):
"""
t: tuple representing an edge
b: origin node
nodes: set of nodes already visited
if we can get to a new node from `b` following `t`
then return that node, else return None
"""
if t[0] == b:
if t[1] not in nodes:
return t[1]
elif t[1] == b:
if t[0] not in nodes:
return t[0]
return None
def connected_nodes(tour):
"""return the set of nodes reachable from
the first node in `tour`"""
a = tour[0][0]
nodes = set([a])
explore = set([a])
while len(explore) > 0:
# see what other nodes we can reach
b = explore.pop()
for t in tour:
node = check_edge(t, b, nodes)
if node is None:
continue
nodes.add(node)
explore.add(node)
return nodes
def is_eulerian_tour(nodes, tour):
# all nodes must be even degree
# and every node must be in graph
degree = get_degree(tour)
for node in nodes:
try:
d = degree[node]
if d % 2 == 1:
print "Node %s has odd degree" % node
return False
except KeyError:
print "Node %s was not in your tour" % node
return False
connected = connected_nodes(tour)
if len(connected) == len(nodes):
return True
else:
print "Your graph wasn't connected"
return False
def test():
nodes = [20, 21, 22, 23, 24, 25]
tour = create_tour(nodes)
return is_eulerian_tour(nodes, tour)
def edge(x, y):
return (x, y) if x < y else (y, x)
def create_tour(nodes):
tour_list = []
n = len(nodes)
for i in range(n):
t = edge(nodes[i], nodes[(i+1) % n])
tour_list.append(t)
return tour_list
print create_tour([0,1,2,3,4,])
print test()
def edge(x, y):
return (x, y) if x < y else (y, x)
def create_tour(nodes):
# there are lots of ways to do this
# a boring solution could just connect
# the first node with the second node
# second with third... and the last with the
# first
tour = []
l = len(nodes)
for i in range(l):
t = edge(nodes[i], nodes[(i+1) % l])
tour.append(t)
return tour
And here is a slightly more complicated solution with some randomness:
from random import randint
def edge(x, y):
return (x, y) if x < y else (y, x)
def poprandom(nodes):
x_i = randint(0, len(nodes) - 1)
return nodes.pop(x_i)
def pickrandom(nodes):
x_i = randint(0, len(nodes) - 1)
return nodes[x_i]
def check_nodes(x, nodes, tour):
for i, n in enumerate(nodes):
t = edge(x, n)
if t not in tour:
tour.append(t)
nodes.pop(i)
return n
return None
def create_tour(nodes):
connected = []
degree = {}
unconnected = [n for n in nodes]
tour = []
# create a connected graph
# first, pick two random nodes for an edge
x = poprandom(unconnected)
y = poprandom(unconnected)
connected.append(x)
connected.append(y)
tour.append(edge(x,y))
degree[x] = 1
degree[y] = 1
# then, pick a random node from the unconnected
# list and create an edge to it
while len(unconnected) > 0:
x = pickrandom(connected)
y = poprandom(unconnected)
connected.append(y)
tour.append(edge(x, y))
degree[x] += 1
degree[y] = 1
# now make sure each node has an even degree.
# have the problem of not adding a duplicate edge
odd_nodes = [k for k, v in degree.items() if v % 2 == 1]
even_nodes = [k for k, v in degree.items() if v % 2 == 0]
# there will always be an even number of odd nodes
# (hint: the sum of degrees of a graph is even)
# so we can just connect pairs of unconnected edges
while len(odd_nodes) > 0:
x = poprandom(odd_nodes)
cn = check_nodes(x, odd_nodes, tour)
if cn is not None:
even_nodes.append(x)
even_nodes.append(cn)
else:
# if we get here
# the node is already connected to
# all the odd nodes so we need to find an
# even one to connect to
cn = check_nodes(x, even_nodes, tour)
# cn cannot be None, and needs to be
# added to the odd_nodes list
odd_nodes.append(cn)
# but, x is now an even node
even_nodes.append(x)
return tour
#4
Advantages:
- a small memory size
- convenient for the construction of algorithms
Disadvantages:
- it does not give a clear idea immediately about a number of edges in a given node
Способы представления графа в информатике
Матрица смежности
Таблица, где как столбцы, так и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу (либо наоборот).
Это наиболее удобный способ представления плотных графов.
Недостатком являются требования к памяти, прямо пропорциональные квадрату количества вершин.
Двумерный массив;
Матрица с пропусками;
Неявное задание
Матрица инцидентности
Основная статья: Матрица инцидентности
Таблица, где строки соответствуют вершинам графа, а столбцы соответствуют связям (рёбрам) графа.
В ячейку матрицы на пересечении строки i со столбцом j записывается:
1 в случае, если связь j «выходит» из вершины i,
−1, если связь «входит» в вершину,
0 во всех остальных случаях (то есть если связь является петлёй или связь не инцидентна вершине)
Данный способ является самым ёмким (размер пропорционален |V| |E|) для хранения, поэтому применяется очень редко, в особых случаях (например, для быстрого нахождения циклов в графе).
Список смежности
Список, где каждой вершине графа соответствует строка, в которой хранится список смежных вершин. Такая структура данных не является таблицей в обычном понимании, а представляет собой «список списков».
Размер занимаемой памяти: O(|V|+|E|).
Это наиболее удобный способ для представления разреженных графов, а также при реализации базовых алгоритмов обхода графа в ширину или глубину, где нужно быстро получать «соседей» текущей просматриваемой вершины.
Список рёбер
Список, где каждому ребру графа соответствует строка, в которой хранятся две вершины, инцидентные ребру.
Размер занимаемой памяти: O(|E|).
Это наиболее компактный способ представления графов, поэтому часто применяется для внешнего хранения или обмена данными.
#9
# Write a function, `count`
# that returns the units of time
# where each print statement is one unit of time
# and each evaluation of range also takes one unit of time
def count(n):
m = 2
if n != 0:
m = count(n-1)
m = m + n
# Your code here to count the units of time
# it takes to execute clique
return m
def clique(n):
print "in a clique..."
for j in range(n):
for i in range(j):
print i, "is friends with", j
print count(5)
# Write a function, `count`
# that returns the units of time
# where each print statement is one unit of time
# and each evaluation of range also takes one unit of time
def count(n):
# Your code here to count the units of time
# it takes to execute clique
return 2 + n * (n + 1) / 2
def clique(n):
print "in a clique..."
for j in range(n):
for i in range(j):
print i, "is friends with", j
#10
# Find Eulerian Tour
#
# Write a function that takes in a graph
# represented as a list of tuples
# and return a list of nodes that
# you would follow on an Eulerian Tour
#
# For example, if the input graph was
# [(1, 2), (2, 3), (3, 1)]
# A possible Eulerian tour would be [1, 2, 3, 1]
graph = [(0, 1), (1, 5), (1, 7), (4, 5), (4, 8), (1, 6), (3, 7), (5, 9), (2, 4), (0, 4), (2, 5), (3, 6), (8, 9)]
def edge(x, y):
return (x, y) if x < y else (y, x)
def get_nodes(graph):
nodes = []
for element in graph:
if element[0] not in nodes:
nodes.append(element[0])
if element[1] not in nodes:
nodes.append(element[1])
return nodes
def diff_list(l1,l2):
diff = []
for element in l1:
if element not in l2:
diff.append(element)
return diff
def create_tour(nodes):
tour_list = []
n = len(nodes)
for i in range(n):
t = edge(nodes[i], nodes[(i+1) % n])
tour_list.append(t)
return tour_list
def get_degree(tour):
degree = {}
for x, y in tour:
degree[x] = degree.get(x, 0) + 1
degree[y] = degree.get(y, 0) + 1
return degree
print get_degree(graph)
def check_edge(t, b, nodes):
"""
t: tuple representing an edge
b: origin node
nodes: set of nodes already visited
if we can get to a new node from `b` following `t`
then return that node, else return None
"""
if t[0] == b:
if t[1] not in nodes:
return t[1]
elif t[1] == b:
if t[0] not in nodes:
return t[0]
return None
def connected_nodes(tour):
"""return the set of nodes reachable from
the first node in `tour`"""
a = tour[0][0]
nodes = set([a])
explore = set([a])
while len(explore) > 0:
# see what other nodes we can reach
b = explore.pop()
for t in tour:
node = check_edge(t, b, nodes)
if node is None:
continue
nodes.add(node)
explore.add(node)
return nodes
def is_eulerian_tour(nodes, tour):
# all nodes must be even degree
# and every node must be in graph
degree = get_degree(tour)
for node in nodes:
try:
d = degree[node]
if d % 2 == 1:
print "Node %s has odd degree" % node
return False
except KeyError:
print "Node %s was not in your tour" % node
return False
connected = connected_nodes(tour)
if len(connected) == len(nodes):
return True
else:
print "Your graph wasn't connected"
return False
print is_eulerian_tour(get_nodes(graph), graph)
def get_way(graph):
node_set = get_nodes(graph)
current_node = node_set[1]
current_edge = graph[0]
visited_edges = [current_edge]
eulerian_tour = [current_edge[0], current_edge[1]]
for v in range(len(graph)/2):
for element in graph[1:]:
for i in range(2):
if i == 0: j =1
else: j = 0
if element not in visited_edges and element[i] == current_node:
eulerian_tour.append(element[j])
visited_edges.append(element)
current_node = element[j]
rest = diff_list(graph,visited_edges)
return eulerian_tour, rest
print get_way(graph)[0]
def find_eulerian_tour(graph):
nodes = get_nodes(graph)
if not is_eulerian_tour(nodes, graph):
print "Your graph has not Eulerian Tour"
return None
result = get_way(graph)[0]
rest = get_way(graph)[1]
if rest == []:
return result
current_result = get_way(rest)[0]
current_rest = get_way(rest)[0]
i = result.index(current_result[0])
result = result[:i] + current_result + result[i+1:]
return result
print find_eulerian_tour(graph)
#############################################################
def edge(x, y):
return (x, y) if x < y else (y, x)
def create_tour(nodes):
# there are lots of ways to do this
# a boring solution could just connect
# the first node with the second node
# second with third... and the last with the
# first
tour = []
l = len(nodes)
for i in range(l):
t = edge(nodes[i], nodes[(i+1) % l])
tour.append(t)
return tour
And here is a slightly more complicated solution with some randomness:
from random import randint
def edge(x, y):
return (x, y) if x < y else (y, x)
def poprandom(nodes):
x_i = randint(0, len(nodes) - 1)
return nodes.pop(x_i)
def pickrandom(nodes):
x_i = randint(0, len(nodes) - 1)
return nodes[x_i]
def check_nodes(x, nodes, tour):
for i, n in enumerate(nodes):
t = edge(x, n)
if t not in tour:
tour.append(t)
nodes.pop(i)
return n
return None
def create_tour(nodes):
connected = []
degree = {}
unconnected = [n for n in nodes]
tour = []
# create a connected graph
# first, pick two random nodes for an edge
x = poprandom(unconnected)
y = poprandom(unconnected)
connected.append(x)
connected.append(y)
tour.append(edge(x,y))
degree[x] = 1
degree[y] = 1
# then, pick a random node from the unconnected
# list and create an edge to it
while len(unconnected) > 0:
x = pickrandom(connected)
y = poprandom(unconnected)
connected.append(y)
tour.append(edge(x, y))
degree[x] += 1
degree[y] = 1
# now make sure each node has an even degree.
# have the problem of not adding a duplicate edge
odd_nodes = [k for k, v in degree.items() if v % 2 == 1]
even_nodes = [k for k, v in degree.items() if v % 2 == 0]
# there will always be an even number of odd nodes
# (hint: the sum of degrees of a graph is even)
# so we can just connect pairs of unconnected edges
while len(odd_nodes) > 0:
x = poprandom(odd_nodes)
cn = check_nodes(x, odd_nodes, tour)
if cn is not None:
even_nodes.append(x)
even_nodes.append(cn)
else:
# if we get here
# the node is already connected to
# all the odd nodes so we need to find an
# even one to connect to
cn = check_nodes(x, even_nodes, tour)
# cn cannot be None, and needs to be
# added to the odd_nodes list
odd_nodes.append(cn)
# but, x is now an even node
even_nodes.append(x)
return tour
Last login: Sat Jun 18 09:02:37 on ttys000
olgabelitskaya (master) ~ $ cd version-control
olgabelitskaya (master) version-control $ git status
On branch master
Your branch is up-to-date with 'exercises/master'.
Untracked files:
(use "git add <file>..." to include in what will be committed)
reflections-cs215/
nothing added to commit but untracked files present (use "git add" to track)
olgabelitskaya (master) version-control $ git add 'reflections-cs215/'
olgabelitskaya (master +) version-control $ git status
On branch master
Your branch is up-to-date with 'exercises/master'.
Changes to be committed:
(use "git reset HEAD <file>..." to unstage)
new file: reflections-cs215/lesson1_reflections_ob.txt
olgabelitskaya (master +) version-control $ git commit -m "Add reflections cs215"
[master 37adbd0] Add reflections cs215
1 file changed, 60 insertions(+)
create mode 100644 reflections-cs215/lesson1_reflections_ob.txt
olgabelitskaya (master) version-control $ git status
On branch master
Your branch is ahead of 'exercises/master' by 1 commit.
(use "git push" to publish your local commits)
nothing to commit, working directory clean
olgabelitskaya (master) version-control $ git push exercises master
Counting objects: 4, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (4/4), done.
Writing objects: 100% (4/4), 5.43 KiB | 0 bytes/s, done.
Total 4 (delta 1), reused 0 (delta 0)
To https://github.com/OlgaBelitskaya/my-exercises.git
56194ea..37adbd0 master -> master
olgabelitskaya (master) version-control $
Eulerian Path and Circuit. Copyright © 2004-2016 Dumitru Ciubatii.
Task:
Given an undirected or a directed graph, find a path or circuit that passes through each edge exactly once.
Solution:
First let's see the conditions for an undirected graph:
An undirected graph has an eulerian circuit if and only if it is connected and each vertex has an even degree (degree is the number of edges that are adjacent to that vertex).
An undirected graph has an eulerian path if and only if it is connected and all vertices except 2 have even degree. One of those 2 vertices that have an odd degree must be the start vertex, and the other one must be the end vertex.
For a directed graph we have:
A directed graph has an eulerian circuit if and only if it is connected and each vertex has the same in-degree as out-degree.
A directed graph has an eulerian path if and only if it is connected and each vertex except 2 have the same in-degree as out-degree, and one of those 2 vertices has out-degree with one greater than in-degree (this is the start vertex), and the other vertex has in-degree with one greater than out-degree (this is the end vertex).
Algorithm for undirected graphs:
Start with an empty stack and an empty circuit (eulerian path).
- If all vertices have even degree - choose any of them.
- If there are exactly 2 vertices having an odd degree - choose one of them.
- Otherwise no euler circuit or path exists.
If current vertex has no neighbors - add it to circuit, remove the last vertex from the stack and set it as the current one. Otherwise (in case it has neighbors) - add the vertex to the stack, take any of its neighbors, remove the edge between selected neighbor and that vertex, and set that neighbor as the current vertex.
Repeat step 2 until the current vertex has no more neighbors and the stack is empty.
Note that obtained circuit will be in reverse order - from end vertex to start vertex.
Algorithm for directed graphs:
Start with an empty stack and an empty circuit (eulerian path).
- If all vertices have same out-degrees as in-degrees - choose any of them.
- If all but 2 vertices have same out-degree as in-degree, and one of those 2 vertices has out-degree with one greater than its in-degree, and the other has in-degree with one greater than its out-degree - then choose the vertex that has its out-degree with one greater than its in-degree.
- Otherwise no euler circuit or path exists.
If current vertex has no out-going edges (i.e. neighbors) - add it to circuit, remove the last vertex from the stack and set it as the current one. Otherwise (in case it has out-going edges, i.e. neighbors) - add the vertex to the stack, take any of its neighbors, remove the edge between that vertex and selected neighbor, and set that neighbor as the current vertex.
Repeat step 2 until the current vertex has no more out-going edges (neighbors) and the stack is empty.
Note that obtained circuit will be in reverse order - from end vertex to start vertex.
Both algorithms will give you the tour in reverse order, i.e. from the end vertex to the start vertex.
As you can see - the algorithms are very similar.
Complexity:
The complexity of both algorithms is O(N+M), where N is the number of vertices and M is the number of edges.
Комментариев нет:
Отправить комментарий