Какие существуют виды графов и на каких примерах их можно рассмотреть?

Некоторые виды графов и примеры, на которых их можно рассмотреть:

1. Ориентированный граф. skillbox.ru В нём каждое ребро указывает своё направление с помощью стрелок. skillbox.ru Пример: схема перелётов определённой авиакомпании, где вершинами графа являются города, а рёбрами — рейсы, соединяющие пары городов. ru.wikipedia.org
2. Неориентированный граф. skillbox.ru В нём рёбра не указывают направление. skillbox.ru Пример: карта метро, где станции — вершины, а перегоны — рёбра. education.yandex.ru
3. Смешанный граф. skillbox.ru Содержит как ориентированные, так и неориентированные рёбра. skillbox.ru Пример: строение Википедии, в котором статьи — вершины графа, а гиперссылки — дуги. ru.wikipedia.org
4. Графы с петлями. skillbox.ru Рёбра графа, которые начинаются и заканчиваются в одной и той же вершине, называются петлями. skillbox.ru Пример: схема связей в социальной сети, где с помощью петли можно показать, что пользователь ставит лайки своим же публикациям. skillbox.ru
5. Мультиграф. skillbox.ru Если между двумя графами существует несколько рёбер, то такой граф будет называться мультиграфом. skillbox.ru Пример: схемы транспортных систем, когда между городами есть несколько разных маршрутов (железная дорога, автомобильная дорога и авиарейсы). skillbox.ru
6. Пустой граф. skillbox.ru Тип графа, который не содержит рёбер. skillbox.ru У него могут быть вершины, но между этими вершинами нет никаких связей. skillbox.ru Пример: в схеме социальных связей так можно изобразить человека, который ни с кем не общается. skillbox.ru
7. Полный граф. skillbox.ru Граф, в котором каждая вершина соединена ребром с каждой другой вершиной. skillbox.ru Пример: коллектив, в котором все знают друг друга. skillbox.ru
8. Взвешенный граф. skillbox.ru Граф, в котором каждому ребру присвоено числовое значение — вес. skillbox.ru Пример: транспортная сеть, в которой рёбрам присвоены весы: они показывают стоимость перевозки груза по ребру и пропускные способности дуг. skysmart.ru
9. Двудольный граф. skillbox.ru Граф, в котором вершины можно разделить на две группы так, что рёбра будут соединять только вершины из разных групп. skillbox.ru Пример: группа студентов и группа курсов, где рёбра — запись студентов на курсы. skillbox.ru
10. Планарный граф. skillbox.ru Граф, который можно нарисовать на плоскости так, чтобы его рёбра пересекались только в вершинах, но не между собой. skillbox.ru

Ещё несколько примеров графов:

• Схема перелётов определённой авиакомпании. ru.wikipedia.org Вершинами графа являются города, а рёбрами — рейсы, соединяющие пары городов. ru.wikipedia.org
• Дерево каталогов в компьютере. ru.wikipedia.org Диски, папки и файлы являются вершинами, а рёбра показывают вложенность файлов и папок в папки и диски. ru.wikipedia.org
• Карта метро, которую можно рассматривать как граф, где станции — вершины, а перегоны — рёбра. education.yandex.ru