Лекция по теории графов

Лекционный материал рекомендуется к изучению по разделу дискретной математики "Теория графов". В лекции рассматриваются следующие понятия: 1. Путь в графе. 2. Связность графов.
Скачать материал
Просмотр
содержимого документа

Занятие 1.

Тема: Понятие пути. Сильно связные графы.

 

Цель занятия: познакомить обучающихся с понятием пути в графе и связностью графов.

План:

  1. Путь в графе.
  2. Связность графов.

Литература:

1.Арасланов, Ш.В. Теория графов. Лекции и практические занятия: учеб.пособие. — Казань: Изд-во Казанск.гос.архитект.- строит.ун-та, 2013. – 87 с.

2.Новиков, Ф.А. Дискретная математика: Учебник для вузов. 2-е изд. Стандарт третьего поколения. — СПб.:Питер, 2013. - 432 с.:ил.

 

Путь в графе

Путём называется последовательность дуг (в ориентированном графе), такая, что конец одной дуги является началом другой дуги.

Путём в ориентированном графе называется последовательность ориентированных рёбер, т. е. для  орграфов цепь называется путём.

Простой путь – путь, в котором ни одна дуга не встречается дважды.

Замкнутый путь в ориентированном графе называется ориентированным циклом или контуром.

Контур – путь, у которого конечная вершина совпадает с начальной вершиной.

Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы).

Цепью называется множество рёбер (в неориентированном графе), которые можно расположить так, что конец (в этом расположении) одного ребра является началом другого.

Другое определение: цепь – последовательность смежных вершин.

Замкнутая цепь называется циклом.

Можно определить простые и элементарные цепи.

Элементарная цепь (цикл, путь, контур), проходящая через все вершины графа называется гамильтоновой цепью.

Простая цепь (цикл, путь, контур), содержащая все рёбра (дуги) графа называется эйлеровой цепью.

Связность графов.

Если любые две вершины графа можно соединить цепью, то граф называется связным.

Если граф не является связным, то его можно разбить на связные подграфы, называемые компонентами.

Связностью графа называется минимальное число рёбер, после удаления которых граф становится несвязным.

Граф называется связным, если любая пара вершин соединена маршрутом.

Несвязный граф состоит из нескольких отдельно связных графов.

Задание 1. Изобразите графически:

  1. Неориентированное и ориентированное ребро;
  2. Неориентированный граф G(V,E), заданный множеством V={v0, v1, v2, v3, v4, v5}     E(v0)={v1,v2}={v0,v2,v4}; E(v1)={v0,v2,v4}; E(v2)={v0,v1,v5}; E(v3)={v4}; E(v5)={v2};
  3. Плоский граф;
  4. Полный неориентированный граф на трех, четырех и пяти вершинах;
  5. Неполный ориентированный граф на пяти вершинах;
  6. Петлю графа;
  7. Неориентированный и ориентированный мультиграф.

 

Решение:

 

         1) Неориентированное ребро                   

 

 

 

 

 

          ориентированное ребро

 

 

 

 

Вопросы для самоконтроля:

 

  1. Что называется, маршрутом, циклом и цепью графа?
  2. Сформулируйте понятие связности графа. Какой граф называют связным?
  3. Перечислите операции над графами.

 

 

Домашнее задание: стр. 5-10, стр. 114 . Подготовить ответы на контрольные вопросы.

1

 

Информация о публикации
Загружено: 17 января
Просмотров: 828
Скачиваний: 6
Карасева Виолетта Сергеевна
Математика, СУЗ, Уроки