ГРАФ_Лаба_4
.docxМИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение высшего образования
«САНКТ-ПЕТЕРБУРГСКИЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ»
КАФЕДРА № 41
ОТЧЕТ ЗАЩИЩЕН С ОЦЕНКОЙ
ПРЕПОДАВАТЕЛЬ
Доц., канд. техн. наук |
|
|
|
Е.А. Бакин |
должность, уч. степень, звание |
|
подпись, дата |
|
инициалы, фамилия |
ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ №4 |
Специальный алгоритм на графах |
по курсу: Построение и анализ графовых моделей |
|
|
РАБОТУ ВЫПОЛНИЛ
СТУДЕНТ ГР. № |
4616 |
|
|
|
А.В.Павлов |
|
|
|
подпись, дата |
|
инициалы, фамилия |
Санкт-Петербург 2019
Цель работы
Реализовать и проверить на тестовом примере специальный алгоритм на графе.
Вариант 7
Алгоритм раскраски графа (невзвешенный неориентированный граф)
Матрица смежности и изображение графа
Матрица смежности
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
Рисунок 1 – Изображение графа
Аналитическое применение графа:
1. Упорядочить вершины по невозрастанию степени.
2. Окрасить первую вершину в цвет 1.
3. Выбрать цвет окраски 1.
4. Пока не окрашены все вершины, повторять п.4.1.-4.2.:
4.1. Окрасить в выбранный цвет всякую вершину, которая не смежна
с другой, уже окрашенной в этот цвет.
4.2. Выбрать следущий цвет.
Для того что бы выполнить алгоритм нам нужно чтобы у двух смежный вершин был разный цвет. Начнем с 0 вершины и окрасим ее в зеленый цвет. Далее переходим на другие вершины и проверяем смежная ли она с ранее окрашенной, далее выбираем другой цвет и повторяем цикл.
Рисунок 2 – Алгоритм раскраски графа
Описание разработанной программы
Листинг программы
import igraph
import numpy as np
import os
def Graf_colors(Graph):
# функции
# поиск всех не смежных вершин
def search_not_adjacant_vertices(vertex, adjacency_graph, vertices_graph):
not_adjacent_vertices = [] # не смежные вершины
# 1. поиск не смежных вершин
for vertex_i, rib_weight_i in enumerate(adjacency_graph[vertex]):
if (not rib_weight_i) and (vertex_i not in vertices_graph):
# 2. исключаем вершины смежные между собой
for vertex_j, rib_weight_j in enumerate(adjacency_graph[vertex_i]):
if rib_weight_j and (vertex_j in not_adjacent_vertices):
break # "Найдена смежная вершина"
else:
not_adjacent_vertices.append(vertex_i) # записываем НЕ смежную вершину
return not_adjacent_vertices
# изначальные данные
vertices_graph = [] # вершины графа
vertices_color = [] # цвет вершин
color = 0 # текущий цвет
# перебираем все вершины графа
for vertex in range(len(Graph)):
print("V-graf: ", vertices_graph, " | V-color: ", vertices_color) ####
# берем не закрашенные вершины
if vertex not in vertices_graph:
for vertex_color in search_not_adjacant_vertices(vertex, Graph, vertices_graph):
print(" v: ", vertex_color) ####
vertices_graph.append(vertex_color)
vertices_color.append(color)
color += 1 # следующий цвет
return tuple(zip(vertices_graph, vertices_color))
# лист смежности
def list_smezh(Vn, matrix):
lst_smz = []
for i in range(Vn):
for j in range(i, Vn):
if matrix[i][j] != 0:
lst_smz += [[tuple([i, j]), matrix[i][j]]]
return lst_smz
# картинка png
def plot_graf(Vn, lst_smz, V_color, fail):
v, color = zip(*V_color)
G = igraph.Graph(directed=False)
G.add_vertices(Vn)
G.vs['label'] = list(range(Vn))
G.vs["color"] = list("#{}{}{}".format(str(hex((80 * color[v.index(k)] + 40) % 201 + 55))[2:],
str(hex((45 * color[v.index(k)] + 120) % 231 + 25))[2:],
str(hex((17 * color[v.index(k)]) % 239 + 16))[2:]) for k in range(Vn))
G.add_edges([i[0] for i in lst_smz])
layout = G.layout('kk')
igraph.plot(G, fail, bbox=(800, 600), layout=layout, vertex_size=40, vertex_label_size=10)
def tests():
def tests_list(tests=[]):
tests.append(np.array([
np.array([0, 1, 0, 1, 0, 1, 0, 0, 0, 0]),
np.array([1, 0, 1, 0, 1, 0, 0, 0, 0, 0]),
np.array([0, 0, 0, 1, 0, 1, 0, 1, 0, 0]),
np.array([0, 0, 1, 0, 1, 0, 1, 0, 0, 0]),
np.array([0, 0, 0, 0, 0, 1, 0, 1, 0, 1]),
np.array([0, 0, 0, 0, 1, 0, 1, 0, 1, 0]),
np.array([0, 1, 0, 0, 0, 0, 0, 1, 0, 1]),
np.array([1, 0, 0, 0, 0, 0, 1, 0, 1, 0]),
np.array([0, 1, 0, 1, 0, 0, 0, 0, 0, 1]),
np.array([1, 0, 1, 0, 0, 0, 0, 0, 1, 0])
])) # тест
return tests
test_list = tests_list() # список тестов, список матриц смежности
# проводим тесты
for index, test in enumerate(test_list):
Vn = len(test) # размер матрицы
lst_smz = list_smezh(Vn, test) # список смежности
# print("\n",lst_smz)
V_color = Graf_colors(test) # цвет вершин
plot_graf(Vn, lst_smz, V_color, 'graph{}.png'.format(index))
os.startfile(r'graph0.png')
G = igraph.Graph(directed=False)
G.add_vertices(10)
G.vs['label'] = list(range(Vn))
G.add_edges([i[0] for i in lst_smz])
layout = G.layout('kk')
igraph.plot(G, 'graph_normal.png', bbox=(800, 600), layout=layout, vertex_size=40, vertex_label_size=10)
os.startfile(r'graph_normal.png')
# print( "\n",V_color )####
tests()
Результат работы
Рисунок 3 – Исходный граф
Рисунок 4 – Окрашенный граф
Выводы:
В ходе лабораторной работы, мы использовать алгоритм раскраски графа. Полученный граф с помощью программы и рассчитанный нами аналитически совпали, что говорит о правильности выполнения программы.
Доп. Вопрос
Построить график зависимости количества цветов для раскраски от количество вершин.
Используем алгоритм созданный в лабораторной работе №3 для генерации графов квадратной решетки c вероятностью p=0.5. Тогда получим такие результаты для 2 тестов для размеров матрицы от 2 до 13