ПРАВОСЛАВНЫЙ СВЯТО-ТИХОНОВСКИЙ БОГОСЛОВСКИЙ УНИВЕРСИТЕТ (БОГОСЛОВСКИЙ ФАКУЛЬТЕТ) Презентация по математике на тему: Элементы теории графов

Элементы теории графов Оглавление Определение графа Определение графа Ориентированные и неориентированные графы Ориентированные и неориентированные графы Пути и маршруты Пути и маршруты Цепь Цепь Длина маршрута Длина маршрута Связность графа Связность графа Матрица смежности Матрица смежности Матрица инцидентности Матрица инцидентности

Элементы теории графов Определение графа Отцом теории графов считается математик Леонард Эйлер, который в 1736 г. решил известную задачу о кенигсбергских мостах. Граф – это множество точек, называемых вершинами, которые соединены линиями.

Элементы теории графов Ориентированные и неориентированные графы В свою очередь линии могут быть: А) Направленными - линии обозначаются стрелками и называются дугами; Б) Ненаправленными – линии называются ребрами. Направленные графы называются ориентированными, а ненаправленные – неориентированными. Направленные графы называются ориентированными, а ненаправленные – неориентированными.

Элементы теории графов Примеры: Неориентированный граф. Вершины: A, B, C, D, с ребрами AC, AD, BC, BD. Ориентированный граф. Вершины: a1,a2…, соединяющие их направленные отрезки - дуги.

Элементы теории графов Ребра, несущие на себе какую-либо информацию, например, настроение, величины расстояния, называют нагруженными. В этом случае можно говорить о графе настроения, дружбы, поездки, поиска преступника и т.д.

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

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

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

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

Элементы теории графов Связность графа Граф называется связанным, если любые две его вершины можно соединить путем (маршрутом). Связный граф. Не связный граф. Связный граф. Не связный граф.

Элементы теории графов Матрица смежности Матрица смежности представляет собой квадратную таблицу, у которой n строк и n столбцов, где n – число вершин графа. Правило построения матрицы смежности для ориентированного (неориентированного) графа : если из вершины 1 в вершину 2 идет n дуг (ребер), то в таблице на пересечении строки с номером 1 и столбца с номером 2 стоит число n, а если нет, то 0.

Элементы теории графов Пример ориентированного графа: Граф. Матрица смежности.

Элементы теории графов Пример неориентированного графа: Граф. Матрица смежности.

Элементы теории графов Матрица инцидентности Матрица инцидентности представляет собой таблицу, у которой число строк равно числу вершин, а число столбцов – числу дуг (ребер) графа. Если граф ориентирован, то на пересечении строки с номером 1 и столбца с номером 2 будет стоять: 1 – если вершина 1 является концом дуги 2; -1 – если вершина 1 является началом дуги 2; 0 – в противном случае. Если граф не ориентирован, то на пересечении строки 1 и столбца 2 будет стоять 1, если вершина 1 принадлежит ребру 2, и 0 – в противном случае.

Элементы теории графов Пример ориентированного графа: Граф. Матрица инцидентности.

Элементы теории графов Пример неориентированного графа: Граф. Матрица инцидентности.

Элементы теории графов Над презентацией работали: Шестаков Вадим Шестаков Вадим Климов Максим Климов Максим 113 группа 113 группа