Всё для Учёбы — студенческий файлообменник
1 монета
ppt

Студенческий документ № 000117 из ДГТУ (бывш. РИСХМ)

Теория графов и ее применение

Введение

ЛЕОНАРД ЭЙЛЕР (1707-1783)

З а д а ч а Э й л е р а

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

П р а в и л о Э й л е р а:

1.В графе, не имеющем вершин нечетных степеней, существует обход всех рёбер (причем каждое ребро проходится в точности один раз) с началом в любой вершине графа.

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

3.В графе, имеющим более двух вершин с нечетной степенью, такого обхода не существует

Основные понятия теории графов.

? Граф - непустое множество V и X- некоторый набор пар элементов из V. Элементы множества V называются вершинами, а элементы набора X- ребрами.

? Подграф - подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. Остовый подграф содержит все вершины графа G.

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

? Взвешенный связный граф - связный граф, с заданной весовой функцией (каждому элементу набора X ставится в соответствие некоторое число - вес ребра).

? Дерево - связный лес (граф не содержащий циклов).

? Остов - остовый подграф, являющийся деревом.

Матрицы на графах

Матрица смежности неориентированного графа

?

Матрица смежности ориентированного графа

? Матрица смежности- матрица размером n(n, элементы которой равны 1, если i-я дуга входит j-ой, и 0 - в противном случае.

? пример:

Матрица инцидентности неориентированного графа

? Матрица инцидентности- матрица размером (n- число вершин, m- число ребер), элементы которой равны 1, если i-я вершина инцидентна j-му ребру, и 0 в противном случае.

? Матрица инцидентности обычно обозначается буквой В

? пример: Матрица инцидентности ориентированного графа

? Матрица инцидентности- матрица размером (n- число вершин, m- число ребер), элементы которой равны 1, если дуга j выходит из вершины i, -1 если дуга j входит в вершины, и 0 в противном случае.

? Матрица инцидентности обычно обозначается буквой В

? пример: Спасибо за уделённое внимание

Показать полностью… https://vk.com/doc-128337234_438473757
543 Кб, 25 октября 2016 в 18:59 - Россия, Ростов-на-Дону, ДГТУ (бывш. РИСХМ), 2016 г., ppt
Рекомендуемые документы в приложении