На головну

Приведення графа до ярусно-паралельній формі

  1.  I. Звіт складається за строго встановленою формою з урахуванням можливості використання обчислювальної техніки для її обробки.
  2.  IX. Змініть наступні пропозиції, вживши дієслова в формі пасивного стану.
  3.  Windows XP на платформі Intel
  4.  XI. Розкривши дужки, вживайте дієслово в потрібній формі (Past Simple Tense, Present Simple Tense, Present Perfect Tense), в дійсному або пасивному стані.
  5.  А. А. Кизеветтер. Внутрішня політика в царювання Миколи Павловича // Історія Росії в XIX столітті. Дореформена Росія. М., 2001.
  6.  А. С. Шишков наводить свідчення вченого іноземця, графа Мейстера.
  7.  Алгоритм Магу для визначення безлічі внутрішньої стійкості графа

Ці міркування мають сенс для орієнтованих графів без контурів.

Граф знаходиться в ярусно-паралельній формі (ЯПФ),

якщо в нульовому ярусі розміщуються вершини, що мають нульову полустепені заходу, в i-тому ярусі - вершини, в які заходять дуги тільки з попередніх ярусів, причому хоча б одна дуга з (i - 1) -го ярусу.

Нехай дано довільний граф без циклів.


a

 h b

 g c

 f d

e

  a b c d e f g h
a              
b                
c              
d            
e            
f              
g            
h            

Алгоритм приведення до ЯПФ:

1. Матриця суміжності графа проглядається, і в черговий ярус вибираються вершини з нульовою полустепені заходу, відповідні нульовим стовпчиках.

2. Рядки, що відповідають вибраним на попередньому кроці вершин, обнуляються.

3. Ви повернетесь до кроку 1, до повного вичерпання матриці.

4. промальовувати дуги.

В результаті, вищенаведений граф набуде вигляду:

d

       
   


 e h

 g f

a

c


b

Ширина ярусу визначається числом вершин в ярусі.

Ширина графа в ЯПФ визначається шириною найбільшого ярусу.




 приклади автоматів |  виходів |  мінімізація автоматів |  Перехід від автомата Мура до автомату Мілі і навпаки |  теорія графів |  теорема Ейлера |  Повні графи і дерева |  дерева |  алгоритм Краскала |  Завдання про 4 фарбах |

© um.co.ua - учбові матеріали та реферати