Міністрерство освіти і науки України
Тернопільський національний технічний університет
імені Івана Пулюя
Кафедра математичних
методів в інженерії
ЗВІТ
до лабораторної роботи №5
з курсу «Сучасні методи розв’язку дискретного програмування»
Правильне розфарбування графа.
Виконав:
ст. гр.
Перевірила:
Крива Н.Р.
Тернопіль 201_
Тема:
Правильне розфарбування графа.
Мета:
Потрібно розфарбувати всі вершини графа мінімальною кількістю фарб.
Текст програми:
%Лабораторна робота №5
%
%Варіант
clear all %очистити память
V=[1 2; 1 1; 2 2; 2 1; 3 2; 3 1; 4 2; 4 1];
E=[1 2 1; 1 3 2; 1 4 3; 2 4 4; 4 3 5; 3 5 6; 3 6 7; 4 6 8; 5 6 9; 6 8 10; 5 7 11; 5 8 12; 7 8 13];
grPlot(V,E,'d'); %Малюємо граф
set(get(gcf,'CurrentAxes'),...
'FontName','Times New Roman Cyr','FontSize',10)
title('\bfВихідний граф')
nCol=grColVer(E);
fprintf('Кольорова вершина\n N вершини N кольору\n');
fprintf(' %2.0f %2.0f\n',['1:length(nCol);nCol']);
grPlot([V,nCol],E,'g','%d','');
set(get(gcf,'CurrentAxes'),...
'FontName','Times New Roman Cyr','FontSize',10)
title('\bfГраф з розфарбованими вершинами')
Рисунок 1 – Вихідний граф
Рисунок 2 – Граф з розфарбованими вершинами
Висновок:
На даній лабораторній роботі було виконане розфарбування всіх вершин графа мінімальною кількістю фарб так, що ніякі суміжні вершини не були розфарбовані одним кольором.