Теория графов
Исследование математической теории о совокупности непустого множества вершин и ребер. Анализ кратности неориентированных и ориентированных дуг. Характеристика понятия эквивалентности при множестве вершин. Обоснование гомеоморфного подразбиения дуги.
| Рубрика | Математика |
| Вид | лекция |
| Язык | русский |
| Дата добавления | 18.10.2013 |
| Размер файла | 89,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Лекция
Теория графов
Рассмотрим чертеж вида:
Обозначения и определения:
V - множество точек - вершины;
X - множество линий - ребра.
Графом называется совокупность множеств вершин и ребер.
v - номер вершины;
{v,w} - обозначение ребра;
{v,v} - петли.
Одинаковые пары - параллельные или кратные ребра;
Кратностью ребер называют количество одинаковых пар.
Пример:
Если в графе есть петли и/или кратные ребра, то такой граф называют псевдографом.
Псевдограф без петель называется мультиграфом.
Мультиграф в котором ни одна пара не встречается более одного раза называется графом.
Если пары (v,w) являются упорядоченными, граф называется ориентированным (орграфом).
Ребра ориентированного графа называются дугами. В неориентированном графе ребра обозначаются неупорядоченной парой - {v,w}. В ориентированном графе дуги обозначаются упорядоченной парой - (v,w).
G, G0 - неориентированный граф, D, D0 - ориентированный.
Обозначают v,w - вершины, x,y,z - дуги и ребра.
Пример:
Тут:
Понятия смежности, инцидентности, степени:
Если x={v,w} - ребро, то v и w - концы ребра x.
Если x=(v,w) - дуга орграфа, то v - начало, w - конец дуги.
Если вершина v является концом ребра x неориентированного графа (началом или концом дуги x орграфа), то v и x называются инцидентными.
Вершины v, w называются смежными, если {v,w}X.
Степенью вершины v графа G называется число (v) ребер графа G, инцидентных вершине v.
Вершина графа, имеющая степень 0 называется изолированной, а степень 1 - висячей.
В неориентированном псевдографе вклад каждой петли инцидентной вершине v в степень вершины v равен 2.
Полустепенью исхода (захода) вершины v орграфа D называется число +(v) дуг орграфа D, исходящих из v (заходящих в v).
В случае ориентированного псевдографа вклад каждой петли инцидентной вершине v равен 1 как в +(v), так и в (v).
Обозначение: n(G), n(D) количество вершин графа, m(G) - количество ребер, m(D) - количество дуг.
Утверждение. Для каждого псевдографа G выполняется равенство:
Для каждого ориентированного псевдографа:
Изоморфизм, гомеоморфизм.
Графы G1=(V1,X1), G2=(V2,X2) называются изоморфными, если биективное (взаимно однозначное) отображение : V1V2, сохраняющее смежность, т. е.:
Орграфы D1=(V1,X1) и D2=(V2,X2) называются изоморфными, если биективное отображение : V1V2, такое, что:
Замечание. Изоморфные графы и орграфы отличаются лишь обозначением вершин. Свойства изоморфных графов:
1) Если изоморфны и : V1V2 биективное отображение, сохраняющее смежность то:
Где:
- количество вершин,
- количество дуг.
Аналогично, если изоморфны и : V1V2 биективное отображение, сохраняющее смежность то выполняется:
Замечание. Для псевдографов и мультиграфов нужно сохранять кратность ребер или дуг. Примеры:
Утверждение. Изоморфизм графов (орграфов) является отношением эквивалентности на множестве графов (орграфов).
Операцией подразбиения дуги (u,v) в орграфе D=(V,X) называется операция, которая состоит в удалении из X дуги (u,v), добавлении к V новой вершины w и добавлении к X\{(u,v)}, двух дуг (u,w) и (w,v).
Аналогично для ребер графа.
Орграф D2 называется подразбиением орграфа D1 если D2 получается из D1 путем последовательного применения операции подразбиения дуг.
Пример.
математический множество гомеоморфный
Орграфы (графы ) называются гомеоморфными, если их подразбиения, которые являются изоморфными.
Определение. Если степени всех вершин графа = k, то граф наз. регулярным степени k. (см. рис. выше).
Граф, состоящий из 1 вершины, называется тривиальным.
Двудольным называется граф G(V,X), такой, что множество вершин V разбито на 2 подмножества V1 и V2 (V1V2=V, V1V2=), причем каждое ребро инцидентно вершине из V1 и V2.
Размещено на Allbest.ru
...Подобные документы
Восстановление графов по заданным матрицам смежности вершин. Построение для каждого графа матрицы смежности ребер, инцидентности, достижимости, контрдостижимости. Поиск композиции графов. Определение локальных степеней вершин графа. Поиск базы графов.
лабораторная работа [85,5 K], добавлен 09.01.2009Рассмотрение понятия и видов графов как совокупности непустого конечного множества элементов; условия их связанности. Доказательства существования замкнутых Эйлеровой, Гамильнотовой и бесконечной цепей. Ознакомление с элементарными свойствами деревьев.
курсовая работа [1,4 M], добавлен 10.02.2012Доказательство тождества с помощью диаграмм Эйлера-Венна. Определение вида логической формулы с помощью таблицы истинности. Рисунок графа G (V, E) с множеством вершин V. Поиск матриц смежности и инцидентности. Определение множества вершин и ребер графа.
контрольная работа [463,0 K], добавлен 17.05.2015Основополагающие понятия теории графов и теории групп. Определение эквивалентности, порождаемой группой подстановок, и доказательство леммы Бернсайда о числе классов такой эквивалентности. Сущность перечня конфигурации, доказательство теоремы Пойа.
курсовая работа [682,9 K], добавлен 20.05.2013Теория динамического программирования. Понятие об оптимальной подструктуре. Независимое и полностью зависимое множество вершин. Задача о поиске максимального независимого множества в дереве. Алгоритм Брона-Кербоша как метод ветвей, границ для поиска клик.
реферат [224,1 K], добавлен 09.10.2012Общее понятие, основные свойства и закономерности графов. Задача о Кенигсбергских мостах. Свойства отношения достижимости в графах. Связность и компонента связности графов. Соотношение между количеством вершин связного плоского графа, формула Эйлера.
презентация [150,3 K], добавлен 16.01.2015Основные понятия, связанные с графом. Решение задачи Эйлера о семи кёнигсбергских мостах. Необходимые и достаточные условия для эйлеровых и полуэйлеровых графов. Применение теории графов к решению задач по математике; степени вершин и подсчёт рёбер.
курсовая работа [713,8 K], добавлен 16.05.2016Граф как множество вершин (узлов), соединённых рёбрами, способы и сфера их применения. Специфика теории графов как раздела дискретной математики. Основные способы преобразования графов, их особенности и использование для решения математических задач.
курсовая работа [1,8 M], добавлен 18.01.2013Основные понятия теории графов. Степень вершины. Маршруты, цепи, циклы. Связность и свойства ориентированных и плоских графов, алгоритм их распознавания, изоморфизм. Операции над ними. Обзор способов задания графов. Эйлеровый и гамильтоновый циклы.
презентация [430,0 K], добавлен 19.11.2013Основные понятия теории графов. Расстояния в графах, диаметр, радиус и центр. Применение графов в практической деятельности человека. Определение кратчайших маршрутов. Эйлеровы и гамильтоновы графы. Элементы теории графов на факультативных занятиях.
дипломная работа [145,5 K], добавлен 19.07.2011Математическое описание системы автоматического управления с помощью графов. Составление графа и его преобразование, избавление от дифференциалов. Оптимизации ориентированных и неориентированных графов, составления матриц смежности и инцидентности.
лабораторная работа [42,2 K], добавлен 11.03.2012Определения понятия множество. Предельная точка множества, предел функции в точке. Эквивалентные, счетные и несчетные множества. Замкнутые и открытые множества. Функции на множестве. Свойства непрерывных функций на замкнутом ограниченном множестве.
курсовая работа [222,3 K], добавлен 11.01.2011Теория графов как раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Основные понятия теории графов. Матрицы смежности и инцидентности и их практическое применение при анализе решений.
реферат [368,2 K], добавлен 13.06.2011Ориентированные и неориентированные графы: общая характеристика, специальные вершины и ребра, полустепени вершин, матрицы смежности, инцидентности, достижимости, связности. Числовые характеристики каждого графа, обход в глубину и в ширину, базис циклов.
курсовая работа [225,5 K], добавлен 14.05.2012Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
курсовая работа [625,4 K], добавлен 30.09.2014Теория графов как математический аппарат для решения задач. Характеристика теории графов. Критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Алгоритм на графах Дейкстры.
контрольная работа [466,3 K], добавлен 11.03.2011Основные понятия теории графов. Содержание метода Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Программная реализация исследуемого алгоритма. Построение матриц смежности и инцидентности.
курсовая работа [228,5 K], добавлен 30.01.2012Основополагающие понятия теории графов. Определение эквивалентности, порождаемое группой подстановок, и доказательство леммы Бернсайда о числе ее классов. Понятие перечня конфигурации и доказательство теоремы Пойа. Решение задачи о перечислении графов.
курсовая работа [649,2 K], добавлен 18.01.2014Спектральная теория графов. Теоремы теории матриц и их применение к исследованию спектров графов. Определение и спектр предфрактального фрактального графов с затравкой регулярной степени. Связи между спектральными и структурными свойствами графов.
дипломная работа [272,5 K], добавлен 05.06.2014Теоретико-множественная и геометрическая форма определения графов. Матрица смежностей вершин неориентированного и ориентированного графа. Элементы матрицы и их сумма. Свойства матрицы инцидентности и зависимость между ними. Подмножество столбцов.
реферат [81,0 K], добавлен 23.11.2008
