Презентация на тему Основные понятия теории графов

цепи и циклы
3.Подграфы
4.Список литературы
Оглавление

линий или ребер, соединяющих между собой все или часть

этих точек. 
Если ребра ориентированы (обычно показывают стрелками) - они называются дугами, и граф с такими ребрами называется ориентированным графом. 

Базовое определение графа и его составляющих

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

что вершины графа изображаются точками, а ребра - линиями,

соединяющими точки






Пустым называется граф без ребер. Полным называется граф, в котором каждые две вершины смежные.

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

это путь, ориентацией дуг которого можно пренебречь.  Цепь – это маршрут, в котором все ребра попарно различны. Цикл - это замкнутый маршрут, являющийся цепью.

Пути, маршруты, цепи и циклы

Пример циклического графа

такой: если от одного числа до другого есть цепь,

ведущая вверх, тогда второе число делится на 2.

Граф и отношения делимости

содержит некоторые вершины исходного графа и некоторые ребра.
Подграф, порожденный

множеством вершин U – это подграф, множество вершин которого - U содержащий те и только те ребра, оба конца которых входят в U.
Граф называется связным, если любая пара его вершин связана.  Связными компонентами графа называются подграфы данного графа, вершины которых связаны.

Подграфы

возникают на практике при изображении различных иерархий. Например, популярны

генеалогические деревья.
Лес – это граф без цикла. Вершины степени 1 в дереве называются листьями. 

Деревья

соответствующих рёбрам.


















Матрица смежности - это матрица n×n где n - число вершин,

где bij = 1, если существует ребро, идещее из вершины х в вершину у и bij = 0 в противном случае.

В теории графов применяются: