Реферат Рішення задач із застосуванням теорії графів

аксимальні паросполучення дводольного графа, помінявши позначення ребер позначеннями вершин:

) 1, 3;

) 1, 5;

) 1, 6;

) 1, 7;

) 2, 5;

) 2, 6;

) 2, 7;

) 3, 4;

) 4, 6;

) 4, 7.

Мінімальні вершинні покриття є доповненнями до максимальних вершинним незалежним множинам:

) 2, 4, 5, 6, 7;

) 2, 3, 4, 6, 7;

) 2, 3, 4, 5, 7;

) 2, 3, 4, 5, 6;

) 1, 3, 4, 6, 7;

) 1, 3, 4, 5, 7;

) 1, 3, 4, 5, 6;

) 1, 2, 5, 6, 7;

) 1, 2, 3, 5, 7;

) 1, 2, 3, 5, 6.

Знайдемо мінімальні вершинні покриття реберного графа за допомогою КНФ. Для даного графа КНФ має вигляд:

f (G p ) = (1v2) (1v4) (2v3) (2v4) (3v5) ( 3v6) (3v7) (4v5) (5v6) (5v7) (6v7). (1)

Перетворимо f (G p ), розкриваючи дужки і використовуючи закон поглинання:

f (G p ) = (1v24) (2v34) (3v567) (6v7) = (12v134v24v234) (35v3467v567v4567) (6v7) = (12v134v24) (356v357v3467v567) = 12356 v 12357 v 123467 v 12567 v v13456 v 13457 v 13467 v 134567 v 23456 v 23457 v 23467 v 24567. (2)

Для перевірки за принципом подвійності складемо для функції (2) двоїсту:

В 

(Gp) = (1v2v3v5v6) (1v2v3v5v7) (1v2v3v4v6v7) (1v2v5v6v7) (1v3v4v5v6) (1v3v4v5v7) (1v3v4v6v7) (1v3v4v5v6v7) (2v3v4v5v6) (2v3v4v5v7) (2v3v4v6v7) (2v4v5v6v7). (3)

Перетворимо функцію (3), використовуючи тотожності поглинання і ідемпотентності. Отримаємо:

(Gp) = (1v2v3v5v6) (1v2v3v5v7) (1v2v3v4v6v7) (1v2v5v6v7) (1v3v4v5v6) (1v3v4v5v7) (1v3v4v6v7) (1v3v4v5v6v7) (2v3v4v5v6) (2v3v4v5v7) (2v3v4v6v7) (2v4v5v6v7) = (1v2v3v5v67) (1v5v6v23v24v37v47) (1v3v4v7v56) (2v3v4v5v67) (2v4v6v7v35) = (1v5v23v24v26v36v37v67) (3v4v12v15v27v57v67v56) (2v4v6v7v35) = (12v13v14v15v35v45v57v67v56v23v24v36v37) (2v4v6v7v35) == 12v14v23v24v35v36v37v45v56v57v67 (4)

Так як функція (4) є двоїстої для функції (1), значить вершинні покриття були знайдені вірно.

Висновок

У даній роботі були вирішені конкретні завдання із застосуванням теорії графів.

Головним завданням було практичне закріплення науково-теоретичних матеріалів теорії графів та отримання навичок застосування отриманих знань для вирішення конкретних завдань.

Назад | сторінка 8 з 9 | Наступна сторінка