Лекция 4 Теория графов



Скачать 34.22 Kb.
Дата01.07.2013
Размер34.22 Kb.
ТипЛекция
Лекция 4
Теория графов
Основные понятия теории графов.
Граф – совокупность множества вершин V и множества пар вида (v,w)X , v,wV. Множество вершин всегда непусто. X – множество ребер.
Ребра бывают петли и кратные.
Псевдограф – граф с петлями и кратными ребрами. Мультиграф – псевдограф без петель.
Граф (просто) – без петель и кратных ребер.
Если пары в X упорядочены, то это ориентированный граф, или орграф. В орграфе ребра называются дугами.
Если ребро x=(v,w), то вершины v и w называются концами ребра, а ребро x соединяет вершины v и w. Если же x – дуга, то v – начало дуги, а w – конец дуги, и говорят, что дуга x исходит из v и заходит в w.
Если вершина является концом или началом дуги (ребра), то вершина и дуга инцидентны.
Вершины смежны, если между ними существует общая дуга, или общее ребро.
Ребра называют смежными, если они имеют общую вершину.
Степенью вершины  называется число ребер, инцидентных этой вершине. Если у вершины ребер нет, это изолированная вершина. Если степень вершины равна 1, то это висячая вершина. Петля увеличивает степень вершины на 2.
Полустепенью исхода (захода) вершины v орграфа называют число + (-) дуг, исходящих из вершины v (заходящих в вершину v). Каждая петля добавляет 1 как в + так и в -.
n-число вершин, m-число ребер.
, так как вклад каждого ребра в эту сумму равен 2.
Для каждого ориентированного псевдографа
Графы G1(v1,w1), G2(v2,w2) изоморфны, если существует биективность (взаимооднозначность) отображения : (v1v2), сохраняющем смежность, т.е.

v,wX1(v),(w)X2. Аналогично для орграфов.
Изоморфные графы (орграфы) отличаются лишь обозначением вершин. У изоморфных графов (орграфов) степени вершин, число вершин, число ребер равны.
Операция подразбиения дуги (u,v) состоит в удалении этой дуги и добавлении двух новых дуг (u,w) и (w,v)
Орграфы (графы) называются гомеоморфными, если существуют их подразбиения, являющиеся изоморфными.
Маршрут в графе (путь в орграфе) это последовательность вершин и ребер v1, x1, v2, x2,…,vk.
У маршрутов существуют подмаршруты. Число ребер в маршруте называется длиной маршрута. Маршрут может быть замкнутым.
Незамкнутый маршрут, в котором все ребра попарно различны называется цепью. Цепь, в которой все вершины попарно различны называется простой цепью.
Замкнутый маршрут, в котором все ребра различны называют циклом. Цикл, в котором все вершины различны называют простым циклом (контуром).
В псевдографе из всякого цикла можно выделить простой цикл.

Доказательство индукцией по k-количеству ребер в цикле.

При k=1 цикл простой.

Пусть при k2 утверждение справедливо для цикла с длиной k-1, докажем его для цикла длиной k. Если в цикле v1…vi….vi…v1 есть одинаковые вершины, то цикл делиться на 2 подцикла. Берем любой подцикл. Если опять есть одинаковые вершины, опять разбиваем, и так пока не получим простой цикл.
Из всякого незамкнутого маршрута можно выделить простую цепь с теми же начальной и конечной вершинами.

Доказательство:

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




Kn- полный граф с n вершинами (каждая вершина соединена со всеми другими).



Полный двудольный граф Kn,m.В одной доли n вершин, в другой m, и каждая вершина соединена со всеми другими из другой доли.




Колесо Wn


Цепь Cn



Платоновы графы (трехмерные).

Похожие:

Лекция 4 Теория графов iconПрограмма дисциплины «теория графов»
Таким образом, теория графов стала существенной частью математического аппарата кибернетики, языком дискретной математики. В значительной...
Лекция 4 Теория графов iconПрограмма наименование дисциплины: Теория конечных графов
Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение методов теории конечных...
Лекция 4 Теория графов iconРабочая программа дисциплины (модуля) Теория графов Направление подготовки
Целями освоения дисциплины (модуля) «Теория графов» являются получение теоретических знаний по основам теории графов
Лекция 4 Теория графов iconПрограмма наименование дисциплины: Теория конечных графов
Цели и задачи дисциплины: Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение...
Лекция 4 Теория графов iconТеория графов и ее приложения
Основные понятия. Графы неориентированные и ориентированные. Способы задания графов. Матрицы смежности и инцидентности графа. Понятие...
Лекция 4 Теория графов iconНаучная работа по теме: 1 глава 1 4 теория графов 4 Эйлеровы графы 7 Задача о мостах, Леонард Эйлер и теория графов 8
Как это сделать? Я стала искать пути решения, и оказалось, что это можно сделать с помощью графов. Раньше понятием «граф» я встречалась...
Лекция 4 Теория графов iconПрограмма наименование дисциплины: Теория графов Рекомендуется для направления (ий) подготовки (специальности (ей))
Курс «Теория графов» является дисциплиной по выбору в бакалаврской программе направления «Прикладная математика и информатика». Курс...
Лекция 4 Теория графов iconБилеты по Дискретной математике «Теория Графов»
Понятие графа (орграфа). Смежность и инцидентность в графе. Классы (типы) графов
Лекция 4 Теория графов iconПрограмма вступительного экзамена в аспирантуру по специальностям 05. 13. 05 "Элементы и устройства вычислительной техники и систем управления"
Комбинаторика и Комбинаторные объекты. Методы комбинаторного анализа. Теория графов. Основные понятия и определения. Способы задания...
Лекция 4 Теория графов iconЛекции по теории графов. М.: Наука, 1990. Берж К. Теория графов и ее применения. М.: Изд иностр лит., 1962
Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. – М.: Наука, 1990
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org