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

Конспект лекции по теме "Ориентированный граф (орграф)"

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

Тема: Ориентированный граф (орграф)

 

Опр.: Граф называется ориентированным, если его рѐбра упорядоченные, т.е. его рѐбра взяты в определѐнном порядке.

Опр.: В орграфе вершины называются узлами, а рѐбра – дугами

image 

Пусть g(v1,E) – орграф, v и w – его вершины.

Опр.: Орграф называется сильносвязным, если для любых двух его вершин v, w существует путь из вершины v в w и из w в v.

Опр.: Орграф называется односторонне связным, если для любых двух его вершин существует путь либо из v в w либо из w в v.

Опр.: Говорят, что вершина w орграфа D достижима из вершины v, если существует путь из вер-

image

шины v в w (путь обозначается < w,v >).

Опр.: Орграф g(v,) называется слабосвязным, если две вершины v и w связаны в графе g, полученном из g отменой ориентации рѐбер.

Опр.: Компоненты сильной связности (КСС) орграфа g – это его максимальные сильносвязные подграфы.

Опр.: Орграф называется несвязным, если он является слабосвязным.

Опр.: Если элементами множества являются необязательно двухэлементные, а любые подмн-ва множества V, то такие элементы мн-ва называются гипердугами, граф называется гиперграфом. Опр.: Если задана функция F: V M и/или F:C M , то множество М называется множеством пометок, граф называется помеченным (или нагруженным).

В качестве множества пометок обычно используются буквы или целые числа.

Опр.: Для орграфа число дуг, исходящих из вершины , называется полустепенью исхода.

Опр.: Для орграфа число дуг, входящих в вершину , называется полустепенью захода.

Обозначаются эти числа, соответственно d() и d() .

1

Опр.: Если в графе ориентировать все рѐбра, то получится орграф, который называется направленным.

Опр.: Направленный орграф, полученный из полного графа, называется турниром.

Опр.: Если в орграфе полустепень захода некоторой вершины = 0 (т.е. d() =0), то такая вершина называется источником.

Опр.: Если в орграфе полустепень исхода некоторой вершины = 0 (т.е. d() =0), то такая вершина называется стоком

Опр.: Цикл в орграфе называется контуром.

Полный граф соответствует универсальному отношению. Граф (неориентированный) соответствует симметричному отношению. Дополнение графов есть дополнение отношений. Изменение направления всех дуг соответствует многоместному отношению. Гиперграф соответствует многоместному отношению между орграфами и бинарными отношениями. В качестве примера связи между орграфами и бинарными отношениями рассмотрим отношения частичного порядка с точки зрения теории графов.

Теорема 1: Если отношение есть строгое частичное упорядочение, то орграф g(v,) не имеет контуров.

Теорема 2: Если орграф g(v,) не имеет контуров, то достижимость есть строгое частичное упорядочение.

Теорема 3: Если орграф не имеет контуров, то в нѐм есть вершина, полустепень захода которой равна 0.

Сильная связность влечѐт одностороннюю связность, которая влечѐт слабую связность. Обратное не верно.

 

 

2

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

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

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

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