Летние международные олимпиады для 1-11 классов Участвовать→
Конкурс разработок «Пять с плюсом» июнь 2021
Добавляйте свои материалы в библиотеку и получайте ценные подарки
Конкурс проводится с 1 июня по 30 июня

Конспект лекции по теме "Количество путей в орграфе"

Данная разработка представляет собой конспект лекции на тему "Количество путей в орграфе" по дисциплине "Элементы математической логики" и раскрывает данную тему. Данный материал может использоваться преподавателями среднеспециальных и высших учебных заведений при изучении данной дисциплины
Просмотр
содержимого документа

Тема: Количество путей в орграфе

 

Опр.: Путём от А1 до Аn в орграфе называется такая последовательность дуг, ведущая от узла А1 до узла Аn, в которой каждые две соседних дуги имеют общий узел и никакая дуга не встречается более одного раза.

Пример 1

В орграфе D определить наибольшее количество путей с общим началом и концом, длина которых не превосходит трѐх.

image 

Решение

Количество путей заданной длины t (в нашем примере t=3) определяется элементами матрицы At(D), где A(D) – матрица смежности. Найдем матрицы A(D), A2(D), A3(D), где A(D) – матрица смежности путей, длина которых равна 1, A2(D) – матрица смежности путей, длина которых равна 2, A3(D)

– матрица смежности путей, длина которых равна 3.

imageimageimageimageimageimage                              0    1    1    0                  00                  0    1    2                10                0   0    1   3

                              0    0    1    1                  00                  0    0    1                20                0   0    0   1

               A(D) 0    0    0    1   1                A2(D) 0     0    0    0   1            A3(D) 0     0   0    0   0

                              0    0    0    0                  10                  0    0    0                00                0   0    0   0

                              0    0    0    0                  00                  0    0    0                00                0   0    0   0

Количество путей из вершины vi в вершину vj, длина которых не превосходит трех, определяется элементом dij матрицы D . Вычисляем эту матрицу:

imageimage                                                                         0   1    2    3   4

                                                                         0   0    1    2   3

               D = A(G) + A2(G) + A3(G) 0    0    0    1    2

                                                                         0   0    0    0   1

                                                                         0   0    0    0   0

Наибольшее число таких путей определяется максимальным элементом (в данном случае он единственный) d15=4, то есть все они имеют началом вершину v1, а концом вершину v5. Выпишем множества путей, удовлетворяющих условию задачи. Среди них:

1)  нуль путей длиной 1

2)  один путь длиной 2 - {(v1v3v5)}

3)  три пути длиной 3 - {(v1v2v4v5), (v1v3v4v5), (v1v2v3v5)}

 

Замечание: Если наибольшее число таких путей с максимальным элементом несколько, то множества путей, удовлетворяющих условию, выписываются для каждого из этих элементов

Информация о публикации
Загружено: 26 марта
Просмотров: 53
Скачиваний: 0
Фоминых Ирина Владимировна
Прочее, СУЗ, Уроки

Проверьте знания своих учеников интересными заданиями

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

Скачать материал