Главная Обратная связь

Дисциплины:






Задания к выполнению работы



Задание 1. Выполнить разложение орграфа на компоненты сильной связности методом Мальгранжа-Томеску.

Задание 2. Произвести раскраску графа, используя функцию смежности Гранди.

Граф задается матрицей смежности. Вариант задания определяется следующим образом: по номеру ijиз таблиц 1-9 берется таблица с номером i, по j из таблицы 10 выбирается строка и осуществляется замена меток {a, b, c, d, e, f, g, h} столбцов матрицы смежности с номером i на цифры из множества {1, 2, 3, 4, 5, 6, 7, 8} в соответствии с табл. 10, затем производится перестановка столбцов матрицы смежности в порядке возрастания номеров. В результате получается матрица смежности требуемого графа.

При раскраске графа его необходимо задать графически.

 

Порядок выполнения работы

1) Изучить теоретическую часть.

2) Выполнить задания по п.6 в соответствии с заданным вариантом.

3) Составить отчет.

4) Ответить на контрольные вопросы.

 

Контрольные вопросы

1) Что называется графом ?

2) Как представляются графы?

3) Что такое матрица смежности?

4) Какие графы подразделяются по связности?

5) Что такое транзитивное замыкание вершин?

6) В чем заключается алгоритм Мальгранжа - Томеску?

7) В чем заключается алгоритм заполнения столбца?

8) Как разложить граф на компоненты сильной связности?

9) В чем состоит задача раскраски графа?

10) В чем заключается алгоритм раскраски графа с помощью функции Гранди?

 

Варианты заданий к выполнению работы

Таблица 1
  A b c d e f g h
     
     
   
             
         
           
         
         
Таблица 2
  a b c d e f g h
           
     
         
   
         
       
             
           
Таблица 3
  a b c d e f g h
         
         
         
         
         
     
       
       
Таблица 4
  a b c d e f g h
       
         
         
         
     
           
           
         

 



Таблица 5
  a b c d e f g h
     
     
         
       
       
           
           
       
Таблица 6
  a b c d e f g h
   
           
       
       
           
           
       
     
Таблица 7
  a b c d e f g h
     
           
           
       
       
       
       
       
Таблица 8
  a b c d e f g h
             
       
           
     
           
       
         
       

 

Таблица 8
  a b c d e f g h
             
       
           
     
           
       
         
       
Таблица 8
  a b c d e f g h
             
       
           
     
           
       
         
       
Таблица 9
  a b c d e f g h
           
           
       
           
         
       
       
       
Таблица 8
  a b c d e f g h
             
       
           
     
           
       
         
       

 

Таблица 10
N варианта a b c d e f g h

 

 


Лабораторная работа N3

Определение чисел внутренней и внешней

Устойчивости графа

Цель работы:

Изучение методов определения внутренне и внешне устойчивых множеств вершин графа, определение чисел устойчивости, цикломатического числа; построение матрицы фундаментальных циклов.

 

Теоретическая часть





sdamzavas.net - 2020 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...