🗊Презентация Теория графов. Определения и примеры. Пути и циклы

Категория: Математика
Нажмите для полного просмотра!
Теория графов. Определения и примеры. Пути и циклы, слайд №1Теория графов. Определения и примеры. Пути и циклы, слайд №2Теория графов. Определения и примеры. Пути и циклы, слайд №3Теория графов. Определения и примеры. Пути и циклы, слайд №4Теория графов. Определения и примеры. Пути и циклы, слайд №5Теория графов. Определения и примеры. Пути и циклы, слайд №6Теория графов. Определения и примеры. Пути и циклы, слайд №7Теория графов. Определения и примеры. Пути и циклы, слайд №8Теория графов. Определения и примеры. Пути и циклы, слайд №9Теория графов. Определения и примеры. Пути и циклы, слайд №10Теория графов. Определения и примеры. Пути и циклы, слайд №11Теория графов. Определения и примеры. Пути и циклы, слайд №12Теория графов. Определения и примеры. Пути и циклы, слайд №13Теория графов. Определения и примеры. Пути и циклы, слайд №14Теория графов. Определения и примеры. Пути и циклы, слайд №15Теория графов. Определения и примеры. Пути и циклы, слайд №16Теория графов. Определения и примеры. Пути и циклы, слайд №17Теория графов. Определения и примеры. Пути и циклы, слайд №18Теория графов. Определения и примеры. Пути и циклы, слайд №19Теория графов. Определения и примеры. Пути и циклы, слайд №20Теория графов. Определения и примеры. Пути и циклы, слайд №21Теория графов. Определения и примеры. Пути и циклы, слайд №22Теория графов. Определения и примеры. Пути и циклы, слайд №23Теория графов. Определения и примеры. Пути и циклы, слайд №24Теория графов. Определения и примеры. Пути и циклы, слайд №25Теория графов. Определения и примеры. Пути и циклы, слайд №26Теория графов. Определения и примеры. Пути и циклы, слайд №27Теория графов. Определения и примеры. Пути и циклы, слайд №28Теория графов. Определения и примеры. Пути и циклы, слайд №29Теория графов. Определения и примеры. Пути и циклы, слайд №30Теория графов. Определения и примеры. Пути и циклы, слайд №31Теория графов. Определения и примеры. Пути и циклы, слайд №32Теория графов. Определения и примеры. Пути и циклы, слайд №33Теория графов. Определения и примеры. Пути и циклы, слайд №34Теория графов. Определения и примеры. Пути и циклы, слайд №35Теория графов. Определения и примеры. Пути и циклы, слайд №36Теория графов. Определения и примеры. Пути и циклы, слайд №37Теория графов. Определения и примеры. Пути и циклы, слайд №38Теория графов. Определения и примеры. Пути и циклы, слайд №39Теория графов. Определения и примеры. Пути и циклы, слайд №40Теория графов. Определения и примеры. Пути и циклы, слайд №41Теория графов. Определения и примеры. Пути и циклы, слайд №42Теория графов. Определения и примеры. Пути и циклы, слайд №43Теория графов. Определения и примеры. Пути и циклы, слайд №44Теория графов. Определения и примеры. Пути и циклы, слайд №45Теория графов. Определения и примеры. Пути и циклы, слайд №46Теория графов. Определения и примеры. Пути и циклы, слайд №47Теория графов. Определения и примеры. Пути и циклы, слайд №48Теория графов. Определения и примеры. Пути и циклы, слайд №49Теория графов. Определения и примеры. Пути и циклы, слайд №50Теория графов. Определения и примеры. Пути и циклы, слайд №51Теория графов. Определения и примеры. Пути и циклы, слайд №52Теория графов. Определения и примеры. Пути и циклы, слайд №53Теория графов. Определения и примеры. Пути и циклы, слайд №54Теория графов. Определения и примеры. Пути и циклы, слайд №55Теория графов. Определения и примеры. Пути и циклы, слайд №56Теория графов. Определения и примеры. Пути и циклы, слайд №57Теория графов. Определения и примеры. Пути и циклы, слайд №58Теория графов. Определения и примеры. Пути и циклы, слайд №59Теория графов. Определения и примеры. Пути и циклы, слайд №60Теория графов. Определения и примеры. Пути и циклы, слайд №61Теория графов. Определения и примеры. Пути и циклы, слайд №62Теория графов. Определения и примеры. Пути и циклы, слайд №63Теория графов. Определения и примеры. Пути и циклы, слайд №64Теория графов. Определения и примеры. Пути и циклы, слайд №65Теория графов. Определения и примеры. Пути и циклы, слайд №66Теория графов. Определения и примеры. Пути и циклы, слайд №67
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Теория графов. Определения и примеры. Пути и циклы. Доклад-сообщение содержит 67 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Теория графов Ирина Борисовна Просвирнина Определения и примеры Пути и циклы
Описание слайда:
Теория графов Ирина Борисовна Просвирнина Определения и примеры Пути и циклы

Слайд 2


Определения и примеры Хотя обычно теорию графов считают одной из современных областей математики, ее начало датируется 1736 годом. В этом году Леонард Эйлер опубликовал свою первую статью, посвященную тому, что сейчас называют теорией графов. В статье Эйлер изложил теорию, позволившую решить задачу о мостах Кенигсберга.
Описание слайда:
Определения и примеры Хотя обычно теорию графов считают одной из современных областей математики, ее начало датируется 1736 годом. В этом году Леонард Эйлер опубликовал свою первую статью, посвященную тому, что сейчас называют теорией графов. В статье Эйлер изложил теорию, позволившую решить задачу о мостах Кенигсберга.

Слайд 3


Определения и примеры Эйлер (1707 – 1783) родился в Швейцарии и провел большую часть жизни в России (Санкт Петербург) и Пруссии (Берлин). Он был одним из самых плодовитых математиков. Собрание его научных трудов составляет более 70 томов.
Описание слайда:
Определения и примеры Эйлер (1707 – 1783) родился в Швейцарии и провел большую часть жизни в России (Санкт Петербург) и Пруссии (Берлин). Он был одним из самых плодовитых математиков. Собрание его научных трудов составляет более 70 томов.

Слайд 4


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

Слайд 5


Определения и примеры Что такое ‘граф’? Интуитивно, граф – это набор точек, называемых ‘вершинами’, и набор линий, называемых ‘ребрами’, при этом каждая линия либо соединяет пару точек, либо соединяет точку саму с собой. Пример графа, знакомый каждому, – карта дорог, на которой города являются вершинами, а соединяющие их дороги – ребрами графа.
Описание слайда:
Определения и примеры Что такое ‘граф’? Интуитивно, граф – это набор точек, называемых ‘вершинами’, и набор линий, называемых ‘ребрами’, при этом каждая линия либо соединяет пару точек, либо соединяет точку саму с собой. Пример графа, знакомый каждому, – карта дорог, на которой города являются вершинами, а соединяющие их дороги – ребрами графа.

Слайд 6


Определения и примеры Определение 1 Неориентированный граф (или просто граф) состоит из конечного непустого множества вершин , конечного множества ребер и функции : E , сопоставляющей каждому ребру подмножество множества , состоящее из одной или двух вершин. При этом говорят, что ребро e соединяет элемент(ы) подмножества .
Описание слайда:
Определения и примеры Определение 1 Неориентированный граф (или просто граф) состоит из конечного непустого множества вершин , конечного множества ребер и функции : E , сопоставляющей каждому ребру подмножество множества , состоящее из одной или двух вершин. При этом говорят, что ребро e соединяет элемент(ы) подмножества .

Слайд 7


Определения и примеры Определение 1 Граф называется простым, если в нем нет петель (т. е. ребер вида ), и нет кратных ребер (т. е. каждая пара различных вершин соединена не более чем одним ребром).
Описание слайда:
Определения и примеры Определение 1 Граф называется простым, если в нем нет петель (т. е. ребер вида ), и нет кратных ребер (т. е. каждая пара различных вершин соединена не более чем одним ребром).

Слайд 8


Определения и примеры
Описание слайда:
Определения и примеры

Слайд 9


Определения и примеры Граф и диаграмма, изображающая граф – это не одно и тоже. Данный граф можно изобразить с помощью двух совершенно различных диаграмм. Например, две диаграммы, представленные на рисунке, изображают один и тот же граф. В этом можно убедиться, построив функцию : E
Описание слайда:
Определения и примеры Граф и диаграмма, изображающая граф – это не одно и тоже. Данный граф можно изобразить с помощью двух совершенно различных диаграмм. Например, две диаграммы, представленные на рисунке, изображают один и тот же граф. В этом можно убедиться, построив функцию : E

Слайд 10


Определения и примеры Определение 2 Вершины и называются смежными, если существует ребро, соединяющее эти вершины. При этом говорят, что каждая из вершин и инцидентна ребру , а ребро инцидентно вершинам и . Ребра , , , называются смежными, если они имеют хотя бы одну общую вершину.
Описание слайда:
Определения и примеры Определение 2 Вершины и называются смежными, если существует ребро, соединяющее эти вершины. При этом говорят, что каждая из вершин и инцидентна ребру , а ребро инцидентно вершинам и . Ребра , , , называются смежными, если они имеют хотя бы одну общую вершину.

Слайд 11


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

Слайд 12


Определения и примеры Определение 2 Степенная последовательность графа – это последовательность степеней его вершин, записанных в неубывающем порядке.
Описание слайда:
Определения и примеры Определение 2 Степенная последовательность графа – это последовательность степеней его вершин, записанных в неубывающем порядке.

Слайд 13


Определения и примеры
Описание слайда:
Определения и примеры

Слайд 14


Определения и примеры
Описание слайда:
Определения и примеры

Слайд 15


Определения и примеры
Описание слайда:
Определения и примеры

Слайд 16


Определения и примеры
Описание слайда:
Определения и примеры

Слайд 17


Определения и примеры
Описание слайда:
Определения и примеры

Слайд 18


Определения и примеры Определение 3 Нулевым графом (или вполне несвязным графом) называется граф с пустым множеством ребер. (Диаграмма нулевого графа – это просто набор точек.) Полным графом называется простой граф, каждая пара различных вершин которого соединена ребром.
Описание слайда:
Определения и примеры Определение 3 Нулевым графом (или вполне несвязным графом) называется граф с пустым множеством ребер. (Диаграмма нулевого графа – это просто набор точек.) Полным графом называется простой граф, каждая пара различных вершин которого соединена ребром.

Слайд 19


Определения и примеры Определение 3 Двудольным графом называется граф, для множества вершин которого имеется разбиение , при чем каждое ребро графа соединяет вершину из с вершиной из . Полный двудольный граф – это двудольный граф, у которого каждая вершина из соединена с каждой вершиной из единственным ребром.
Описание слайда:
Определения и примеры Определение 3 Двудольным графом называется граф, для множества вершин которого имеется разбиение , при чем каждое ребро графа соединяет вершину из с вершиной из . Полный двудольный граф – это двудольный граф, у которого каждая вершина из соединена с каждой вершиной из единственным ребром.

Слайд 20


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

Слайд 21


Определения и примеры Примеры Полный граф с вершинами можно описать следующим образом. Он имеет множество вершин , множество ребер и функцию заданную правилом: . Граф является регулярным степени , так как каждая вершина связана единственным ребром с остальными вершинами.
Описание слайда:
Определения и примеры Примеры Полный граф с вершинами можно описать следующим образом. Он имеет множество вершин , множество ребер и функцию заданную правилом: . Граф является регулярным степени , так как каждая вершина связана единственным ребром с остальными вершинами.

Слайд 22


Определения и примеры Примеры Полные графы с тремя, четырьмя и пятью вершинами приведены на следующем рисунке.
Описание слайда:
Определения и примеры Примеры Полные графы с тремя, четырьмя и пятью вершинами приведены на следующем рисунке.

Слайд 23


Определения и примеры Примеры Пусть – двудольный граф, для множества вершин которого имеется разбиение . Заметим, что не обязан быть простым графом. Требуется только, чтобы каждое ребро соединяло вершину из с вершиной из . Данные вершины и могут быть либо вообще не соединены ребрами, либо соединены более чем одним ребром. Ясно, что в двудольном графе тем не менее, нет петель.
Описание слайда:
Определения и примеры Примеры Пусть – двудольный граф, для множества вершин которого имеется разбиение . Заметим, что не обязан быть простым графом. Требуется только, чтобы каждое ребро соединяло вершину из с вершиной из . Данные вершины и могут быть либо вообще не соединены ребрами, либо соединены более чем одним ребром. Ясно, что в двудольном графе тем не менее, нет петель.

Слайд 24


Определения и примеры Примеры Полный двудольный граф полностью специфицируется числами и ||. Если и , то полный двудольный граф обозначается через и называется полным двудольным графом от и вершин. Граф является простым.
Описание слайда:
Определения и примеры Примеры Полный двудольный граф полностью специфицируется числами и ||. Если и , то полный двудольный граф обозначается через и называется полным двудольным графом от и вершин. Граф является простым.

Слайд 25


Определения и примеры Примеры На рисунке изображены два двудольных графа. В обоих случаях вершины из представлены закрашенными окружностями, а вершины из – крестиками. Граф, изображенный на рисунке (b) – это полный двудольный граф .
Описание слайда:
Определения и примеры Примеры На рисунке изображены два двудольных графа. В обоих случаях вершины из представлены закрашенными окружностями, а вершины из – крестиками. Граф, изображенный на рисунке (b) – это полный двудольный граф .

Слайд 26


Определения и примеры Определение 4 Пусть – граф с множеством вершин . Матрица смежности графа – это матрица , состоящая из элементов , равных числу ребер, соединяющих и .
Описание слайда:
Определения и примеры Определение 4 Пусть – граф с множеством вершин . Матрица смежности графа – это матрица , состоящая из элементов , равных числу ребер, соединяющих и .

Слайд 27


Определения и примеры Матрица смежности симметрична, так как число ребер, соединяющих и равно числу ребер, соединяющих и .
Описание слайда:
Определения и примеры Матрица смежности симметрична, так как число ребер, соединяющих и равно числу ребер, соединяющих и .

Слайд 28


Определения и примеры Степень вершины легко определить с помощью матрицы смежности. Если при вершине нет петель, то ее степень равна сумме элементов -го столбца (или -ой строки) матрицы смежности. Так как при вычислении степени вершины каждая петля, инцидентная данной вершине, учитывается дважды, то, суммируя элементы -го столбца (или -ой строки) матрицы смежности, диагональный элемент следует умножить на 2.
Описание слайда:
Определения и примеры Степень вершины легко определить с помощью матрицы смежности. Если при вершине нет петель, то ее степень равна сумме элементов -го столбца (или -ой строки) матрицы смежности. Так как при вычислении степени вершины каждая петля, инцидентная данной вершине, учитывается дважды, то, суммируя элементы -го столбца (или -ой строки) матрицы смежности, диагональный элемент следует умножить на 2.

Слайд 29


Определения и примеры
Описание слайда:
Определения и примеры

Слайд 30


Определения и примеры
Описание слайда:
Определения и примеры

Слайд 31


Определения и примеры
Описание слайда:
Определения и примеры

Слайд 32


Определения и примеры
Описание слайда:
Определения и примеры

Слайд 33


Определения и примеры
Описание слайда:
Определения и примеры

Слайд 34


Определения и примеры Примеры Матрица смежности нулевого графа с вершинами – нулевая матрица , так как у нулевого графа нет ребер.
Описание слайда:
Определения и примеры Примеры Матрица смежности нулевого графа с вершинами – нулевая матрица , так как у нулевого графа нет ребер.

Слайд 35


Определения и примеры Примеры Матрица смежности полного графа – матрица с нулями на главной диагонали (так как нет петель) и единицами на остальных позициях (так как каждая пара различных вершин соединена единственным ребром).
Описание слайда:
Определения и примеры Примеры Матрица смежности полного графа – матрица с нулями на главной диагонали (так как нет петель) и единицами на остальных позициях (так как каждая пара различных вершин соединена единственным ребром).

Слайд 36


Определения и примеры Определение 5 Граф называют подграфом графа и пишут: , если , и для каждой вершины из .
Описание слайда:
Определения и примеры Определение 5 Граф называют подграфом графа и пишут: , если , и для каждой вершины из .

Слайд 37


Определения и примеры Условие: для каждого ребра из – означает, что ребра подграфа должны соединять те же вершины, которые они соединяют в графе . На интуитивном уровне является подграфом графа , если диаграмму графа можно получить из диаграммы графа, удаляя вершины и/или ребра из диаграммы графа . Конечно, если мы удаляем вершину, то мы должны удалить все ребра, инцидентные данной вершине.
Описание слайда:
Определения и примеры Условие: для каждого ребра из – означает, что ребра подграфа должны соединять те же вершины, которые они соединяют в графе . На интуитивном уровне является подграфом графа , если диаграмму графа можно получить из диаграммы графа, удаляя вершины и/или ребра из диаграммы графа . Конечно, если мы удаляем вершину, то мы должны удалить все ребра, инцидентные данной вершине.

Слайд 38


Определения и примеры Пример Граф является подграфом графа .
Описание слайда:
Определения и примеры Пример Граф является подграфом графа .

Слайд 39


Пути и циклы По аналогии с дорожной картой мы можем рассматривать различные типы ‘путешествий’ в графе. Например, если граф представляет сеть дорог, связывающих различные города, то можно задаться следующим вопросом. Можно ли совершить путешествие, которое начинается и заканчивается в одном и том же городе, посетив при этом каждый город только один раз и проезжая по каждой дороге не более одного раза. Как всегда, начнем с определений.
Описание слайда:
Пути и циклы По аналогии с дорожной картой мы можем рассматривать различные типы ‘путешествий’ в графе. Например, если граф представляет сеть дорог, связывающих различные города, то можно задаться следующим вопросом. Можно ли совершить путешествие, которое начинается и заканчивается в одном и том же городе, посетив при этом каждый город только один раз и проезжая по каждой дороге не более одного раза. Как всегда, начнем с определений.

Слайд 40


Пути и циклы Определение 6 Последовательность ребер длины в графе – это последовательность (не обязательно различных) ребер , таких, что и являются смежными для . Последовательность ребер определяет последовательность вершин (опять, не обязательно различных) , где (). Мы говорим, что – начальная вершина и – конечная вершина последовательности ребер.
Описание слайда:
Пути и циклы Определение 6 Последовательность ребер длины в графе – это последовательность (не обязательно различных) ребер , таких, что и являются смежными для . Последовательность ребер определяет последовательность вершин (опять, не обязательно различных) , где (). Мы говорим, что – начальная вершина и – конечная вершина последовательности ребер.

Слайд 41


Пути и циклы Определение 6 Путь – это последовательность ребер, в которой все ребра различны. Если к тому же и все вершины различны (возможно, кроме ), то путь называется простым. Последовательность ребер называется замкнутой, если . Простой замкнутый путь, состоящий по крайней мере из одного ребра, называется циклом.
Описание слайда:
Пути и циклы Определение 6 Путь – это последовательность ребер, в которой все ребра различны. Если к тому же и все вершины различны (возможно, кроме ), то путь называется простым. Последовательность ребер называется замкнутой, если . Простой замкнутый путь, состоящий по крайней мере из одного ребра, называется циклом.

Слайд 42


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

Слайд 43


Пути и циклы
Описание слайда:
Пути и циклы

Слайд 44


Пути и циклы
Описание слайда:
Пути и циклы

Слайд 45


Пути и циклы
Описание слайда:
Пути и циклы

Слайд 46


Пути и циклы
Описание слайда:
Пути и циклы

Слайд 47


Пути и циклы
Описание слайда:
Пути и циклы

Слайд 48


Пути и циклы
Описание слайда:
Пути и циклы

Слайд 49


Пути и циклы
Описание слайда:
Пути и циклы

Слайд 50


Пути и циклы Вычислим квадрат матрицы смежности :
Описание слайда:
Пути и циклы Вычислим квадрат матрицы смежности :

Слайд 51


Пути и циклы
Описание слайда:
Пути и циклы

Слайд 52


Пути и циклы
Описание слайда:
Пути и циклы

Слайд 53


? В матрице -элемент равен числу последователь-ностей ребер длины , соединяющих и . -элемент из получается ‘умножением’ -ой строки на -ый столбец матрицы , т. е. . -ое слагаемое этой суммы: – это произведение числа ребер, соединяющих и , на число ребер, соединяющих и ; другими словами, – это число последовательностей ребер длины 2, соединяющих и и проходящих через . Суммируя по всем , получим число всех последовательностей ребер длины 2, соединяющих и .
Описание слайда:
? В матрице -элемент равен числу последователь-ностей ребер длины , соединяющих и . -элемент из получается ‘умножением’ -ой строки на -ый столбец матрицы , т. е. . -ое слагаемое этой суммы: – это произведение числа ребер, соединяющих и , на число ребер, соединяющих и ; другими словами, – это число последовательностей ребер длины 2, соединяющих и и проходящих через . Суммируя по всем , получим число всех последовательностей ребер длины 2, соединяющих и .

Слайд 54


Пути и циклы Вычислим куб матрицы смежности
Описание слайда:
Пути и циклы Вычислим куб матрицы смежности

Слайд 55


Пути и циклы
Описание слайда:
Пути и циклы

Слайд 56


Пути и циклы
Описание слайда:
Пути и циклы

Слайд 57


Пути и циклы Теорема 1 Пусть – граф с множеством вершин и матрицей смежности . - элемент матрицы равен числу последовательностей ребер длины , соединяющих и . Доказательство Теорема может быть доказана методом математической индукции. Индуктивный шаг проводится аналогично разобранному выше случаю.
Описание слайда:
Пути и циклы Теорема 1 Пусть – граф с множеством вершин и матрицей смежности . - элемент матрицы равен числу последовательностей ребер длины , соединяющих и . Доказательство Теорема может быть доказана методом математической индукции. Индуктивный шаг проводится аналогично разобранному выше случаю.

Слайд 58


Пути и циклы На интуитивном уровне ясно, что некоторые графы являются ‘единым целым’, а другие состоят из нескольких частей. Объясним эту ситуацию, используя понятие пути.
Описание слайда:
Пути и циклы На интуитивном уровне ясно, что некоторые графы являются ‘единым целым’, а другие состоят из нескольких частей. Объясним эту ситуацию, используя понятие пути.

Слайд 59


Пути и циклы Определение 7 Граф называется связным, если для любых двух его различных вершин существует путь, связывающий эти вершины.
Описание слайда:
Пути и циклы Определение 7 Граф называется связным, если для любых двух его различных вершин существует путь, связывающий эти вершины.

Слайд 60


Пути и циклы Произвольный граф разбивается на несколько связных подграфов, называемых его (связными) компонентами. Компоненты можно определить формально как максимальные связные подграфы. Другими словами, является компонентой графа , если – связный подграф графа , и если не является собственным подграфом любого другого связного собственного подграфа графа . Это второе условие выражает значение термина «максимальный связный подграф»; оно утверждает, что если – связный собственный подграф графа , такой, что , то . Таким образом, не существует cвязного собственного подграфа графа , который ‘больше’, чем .
Описание слайда:
Пути и циклы Произвольный граф разбивается на несколько связных подграфов, называемых его (связными) компонентами. Компоненты можно определить формально как максимальные связные подграфы. Другими словами, является компонентой графа , если – связный подграф графа , и если не является собственным подграфом любого другого связного собственного подграфа графа . Это второе условие выражает значение термина «максимальный связный подграф»; оно утверждает, что если – связный собственный подграф графа , такой, что , то . Таким образом, не существует cвязного собственного подграфа графа , который ‘больше’, чем .

Слайд 61


Пути и циклы Компоненты графа – это его связные ‘куски’. В частности, связный граф имеет только одну компоненту. Разложение графа на связные компоненты часто бывает очень полезным. Обычно проще доказывать результаты для связных графов, а потом переносить доказанные свойства на произвольные графы, рассматривая по очереди все их связные компоненты.
Описание слайда:
Пути и циклы Компоненты графа – это его связные ‘куски’. В частности, связный граф имеет только одну компоненту. Разложение графа на связные компоненты часто бывает очень полезным. Обычно проще доказывать результаты для связных графов, а потом переносить доказанные свойства на произвольные графы, рассматривая по очереди все их связные компоненты.

Слайд 62


Пути и циклы Имеется альтернативный способ определения компонент графа . Определим отношение на следующим образом: тогда и только тогда, когда и можно соединить путем в . Если трактовать пустой путь как путь, не содержащий ребер, то легко видеть, что является отношением эквивалентности.
Описание слайда:
Пути и циклы Имеется альтернативный способ определения компонент графа . Определим отношение на следующим образом: тогда и только тогда, когда и можно соединить путем в . Если трактовать пустой путь как путь, не содержащий ребер, то легко видеть, что является отношением эквивалентности.

Слайд 63


Пути и циклы тогда и только тогда, когда и можно соединить путем в . ? является отношением эквивалентности.
Описание слайда:
Пути и циклы тогда и только тогда, когда и можно соединить путем в . ? является отношением эквивалентности.

Слайд 64


Пути и циклы Единственная трудность состоит в доказательстве транзитивности отношения . Если – путь из в , а – путь из в , тогда последовательность ребер ‘путь , за которым следует путь ’ – это последовательность ребер из в . Однако, эта последовательность ребер может и не быть путем, так пути и могут состоять из одинаковых ребер. В этом случае из последовательности ребер следует удалить некоторые ребра, чтобы построить искомый путь из в
Описание слайда:
Пути и циклы Единственная трудность состоит в доказательстве транзитивности отношения . Если – путь из в , а – путь из в , тогда последовательность ребер ‘путь , за которым следует путь ’ – это последовательность ребер из в . Однако, эта последовательность ребер может и не быть путем, так пути и могут состоять из одинаковых ребер. В этом случае из последовательности ребер следует удалить некоторые ребра, чтобы построить искомый путь из в

Слайд 65


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

Слайд 66


Пути и циклы
Описание слайда:
Пути и циклы

Слайд 67


Пути и циклы Пример Часто по диаграмме графа легко определить число его компонент. Однако, так бывает не всегда. Например, оба графа, изображенные на рисунке, имеют две компоненты, хотя для графа (b) это не столь очевидно.
Описание слайда:
Пути и циклы Пример Часто по диаграмме графа легко определить число его компонент. Однако, так бывает не всегда. Например, оба графа, изображенные на рисунке, имеют две компоненты, хотя для графа (b) это не столь очевидно.

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию