Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой




Скачать 338.77 Kb.
Название Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой
страница 2/4
Дата публикации 21.05.2014
Размер 338.77 Kb.
Тип Методическое пособие
literature-edu.ru > Математика > Методическое пособие
1   2   3   4


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

Определение 1.Граф представляет собой непустое конечное множество вершин V и множество ребер E, оба конца которых принадлежат множеству V.

Обозначение графа: G(V,E).

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


Рис.3 Примеры графов

Определение 2.Вершины, из которых выходит нечетное число ребер, называются нечетными, а вершины, из которых выходит четное число ребер, называются четными.

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

Определение 4. Два ребра, инцидентные одной вершине, называются смежными. Две вершины, инцидентные одному ребру, также называются смежными.

Определение 5. Нулевой граф– схема, состоящая из изолированных вершин.

Определение 6. Неполный граф - граф, в котором не построены все возможные ребра.

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

Неполный граф Полный граф

Рис.4
Определение 8. Два графа называются изоморфными, если у них одинаковое количество вершин и если вершины одного графа соединены ребром, то и соответствующие им вершины другого графа тоже соединены ребром, то есть существует взаимно-однозначное соответствие между их ребрами и вершинами – соответствующие ребра соединяют соответствующие вершины.

Определение 9. Плоский граф – это граф, который можно начертить так, чтобы его ребра пересекались только в вершинах.

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



Первоначальный планарный Изображенный иначе плоский

граф

Рис.5


Определение 11. Маршрут в графе - чередующаяся последовательность вершин и ребер, которая начинается и заканчивается вершиной.

Определение 12. Цикл – маршрут, в котором первая вершина совпадает с последней.

Определение 13. Контур – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней.

Определение 14. Путь – маршрут без повторения вершин.


Маршрут – 1,2,3,4,2,5

Путь – 1,2,3,4,7,5

Цикл -1,2,3,4,2,5,6,1

Контур-1,2,5,6,1


Рис.6
Связность графов
Определение 15. Две вершины графа называются связными, если в графе существует путь с концами в этих вершинах. Если такого пути не существует, вершины называются не связными.

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


На рисунке любая пара вершин, взятая из набора А,Б,В,Г,Д ,будет связной, т.к. от любой из них к любой можно "пройти" по ребрам графа. Пары вершин, одна из которых взята из набора А,Б,В,Г,Д, а другая из набора Е,Ж,З, не будут связными, т.к. от одной к другой "пройти" по ребрам не удается.
Определение 17. Мост – ребро, при удалении которого граф перестает быть связным.



Рис.7

Деревья
Определение 18. Дерево–конечный связный граф с выделенной вершиной (корнем), не имеющий циклов.Договоримся считать «деревом» и всякий граф, состоящий из одной (изолированной) вершины.

Определение 19. Степень вершины – число ребер, выходящих из нее. Если степень вершины равна 1, то вершина называется висячей.



Рис.8
Свойства дерева.
Свойство 1.Для каждой пары вершин дерева существует единственный путь, их соединяющий.

Этим свойством пользуются при нахождении всех предков, например, по мужской линии, любого человека, чья родословная представлена в виде генеалогического дерева, которое является «деревом» и в смысле теории графов.

И.П.Толстой

(1726)

П.М.Ртищева

(1748)

Княжна

А.И.Щеткина

Княжна

П.Н.Горчакова

(1762-1838)

Граф

А.И.Толстой

(1721-1803)

Граф

И.А.Толстой

(1787-1820)

Граф

Н.И.Толстой

(1794-1837)

М.Д.Чаадаев

(1794-1856)

Князь

Н.С.Волконский

(1753-1826)

Граф

Л.Н.Толстой

(1828-1910)

Княжна

М.И.Волконская

(1726)

Княжна

Е.Д.Трубецкая

(1749-1799)


Рис.9 Генеалогическое дерево Л.Н.Толстого



Свойство 2.Всякое ребро в дереве является мостом. После удаления любого ребра дерева, оно «распадается» на два дерева.

Наиболее характерные свойства деревьев, которые одновременно служат эквивалентными определениями дерева, сформулированы в теореме:

Теорема. Граф G = (V,X) является деревом тогда и только тогда, когда выполняется хотя бы одно из условий:

граф G = (V,X) связен и не содержит циклов;

граф G = (V,X) не содержит циклов и имеет n-1 ребро;

граф G = (V,X) связен и имеет n-1 ребро;

граф G = (V,X) не содержит циклов, но добавление ребра между смежными вершинами приводит к появлению одного и только одного элементарного цикла;

граф G = (V,X) связный, но утрачивает это свойство после удаления любого ребра;

в графе G = (V,X) всякая пара вершин соединена цепью, притом только одной.

Ориентированные графы

Определение 20. Ребро графа называется ориентированным ребром, если одну из его вершин считать началом, а другую концом этого ребра.

Определение 21. Граф, у которого все ребра ориентированные, называется ориентированным графом.
На практике часто ориентированные графы используют для наглядного представления процесса и результата спортивных соревнований.



Рис 10а. Рис. 10б.

Так, на рисунке 10а изображена (с помощью графа) схема игр между командами А, Б, В, Г, Д, Е. Но эта схема не дает информации о результатах игры. Обычно используют ориентацию ребра от выигравшей команды к проигравшей,т. е. если А выиграла у Д, то граф ориентируют от А к Д. На рисунке 10б(с помощью ориентированного графа) показаны результаты игр между командами, изображенными с помощью графа на предыдущем рисунке.

Определение 22. Граф называется смешанным, если в нем есть ориентированные и неориентированные ребра.

Эйлеровы графы

Определение 23. Эйлеровым путем в графе называется путь, содержащий все ребра графа.

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

Определение 25. Эйлеров граф – это граф, обладающий эйлеровым циклом.

Определение 26. Полуэйлеров граф – это граф, содержащий маршрут, обходящий все ребра по одному разу.



Не является Полуэйлеров Эйлеров граф

эйлеровым

Рис.11

Теоремы Эйлера

Теорема 1. Для того, чтобы связный граф являлся эйлеровым, необходимо и достаточно, чтобы степени всех его вершин были четными.

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

  • К задачам на эйлеровы графы относятся головоломки, в которых требуется вычертить на плоскости одним росчерком замкнутые кривые, обводя каждый участок один раз.

  • На практике эйлеровым графом может быть план выставки; это позволяет расставить указатели маршрута так, чтобы посетитель смог пройти по каждому залу в точности по одному разу.

  • Маршрут почтальона, разносящего заказные письма, газеты, журналы и другую корреспонденцию тоже можно составить в виде эйлерова графа; это позволит экономить силы и время.

  • Поливка улиц одной машиной или сбор мусора

  • Уборка помещений и коридоров в больших помещениях


Гамильтоновы графы

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

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

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




V9 V2 V4 V3 V5 V1 V7

V6 V8 V10 V12 V11 V9

Гамильтоновый цикл

V1 V2 V3 V4 V1 V5 –

не является

гамильтоновым путем

V1 V2 V3 V4 V1 V5 –

гамильтонов путь




Рис.12

Операции над графами

В ряде задач теории графов используются двуместные операции над графами.

Рассмотрим графы G1=(V1,X1) и G2=(V2,X2).
1. Объединением графов G1=(V1,E1) и G2=(V2,X2)называется граф G = G1UG2, множество вершин которого V = V1UV2, а множество ребер X = X1UX2.
2. Пересечением графов G1=(V1,E1) и G2=(V2,X2) называется граф G = G1∩ G2, множество вершин которого V = V1 ∩ V2 , а множество ребер X = X1 ∩ X2.
3. Подграфом графа G= (V,X) называется граф G1=(V1,X1), все вершины и ребра которого являются подмножествами множества вершин и ребер графа G, то есть G1 G, если V1 V, X1X.
4. Кольцевой суммой двух графов называется граф G = G1G2, порожденный множеством вершин V = V1 U V2 и множеством ребер (X1 U X2) \ (X1 ∩ X2), то есть множеством ребер , содержащихся либо в G1, либо в G2 , но не в G1∩ G2.


Примеры на операции над графами:

а) G1 б) G2
в) г)


Рис.13 Операции над графами:

а)-граф G1 ; б)-граф G2;

в)-объединение графов G1 и G2;

г)-пересечение графов G1 и G2;

д)-кольцевая сумма графов G1 и G2





Способы задания графов

Существуют различные способы задания графа:

1. Геометрический – рисунки, схемы, диаграммы.

Определение 30. Геометрическое представление плоского графа называется его реализацией.

Человеку удобно работать с графом – рисунком, так он может легко установить связь между вершинами в наглядном виде с помощью ребер, изображаемых непрерывными линиями.

2. Перечислительный– простое перечисление вершин и ребер.

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

Такой способ удобен для машинной обработки графа, сжатия и хранения информации графа.

Рассмотрим более подробно матричный способ.

Пусть задан граф G(V;X), где
V ={V1,V2,…Vn} – вершины,X = {x1,x2,…xn} – ребра.

I. Матрица инцидентности – таблица, состоящая из n строк (вершины) и m столбцов (ребра), в которой:

а) для неориентированного графа:

  • bij = 1, если вершина Vij инцидентна ребру xij

  • bij = 0, в противном случае.

б) для ориентированного графа:

  • bij = 1, если вершина Vi является началом ребра xj;

  • bij = 0, если вершина Vi не инцидентна ребру xj;

  • bij = - 1, если вершина Vi является концом ребра xj.

Очевидно, что в каждом столбце матрицы инцидентности должно быть только два ненулевых числа, так как ребро инцидентно двум вершинам. Число ненулевых элементов каждой строки – степень соответствующей вершины.

Таблица инцидентности графа, изображенного на рисунке.

Vi

xj

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

V1

V2

V3

V4

V5

V6

1

0

0

0

0

1

1

1

0

0

0

0

0

1

1

0

0

0

0

0

1

1

0

0

0

0

0

0

1

1

0

0

1

0

1

0

0

0

1

0

0

1

0

1

0

0

0

1

0

1

0

0

1

0

0

0

0

1

0

1

Матрица инцидентности для данного графа.

1100000000

0110000110

В = 0011011000

0001000001

0000110010

1000101101

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

II. Матрица смежности – квадратная таблица, порядка n(n×n), в которой

а) для неориентированного графа:

  • aij = 1, если вершинысмежные

  • аij = 0, в противном случае.

Хотя формально каждая вершина всегда смежна сама с собой, в матрице смежности аkk= 0, если нет петли, и аkk= 1, если есть одна петля. Итак, если граф имеет матрицу смежности и не имеет петель, на главной диагонали у него всегда стоят нули.

Таблица смежности графа, изображенного на рисунке.

Vi

Vi

V1

V2

V3

V4

V5

V6

V1

V2

V3

V4

V5
V6

0

1

0

1

0

1

1

0

1

1

0

1

0

1

0

1

1

1

1

1

1

0

0

1

0

0

1

0

0

1

1

1

1

1

1

0



Матрица смежности для данного графа.

010101

101101

010111

А= 111001

001001

111110

Задача. Граф задан матрицей смежности А. Построить диаграмму этого графа, если

000100

001101

А = 011010

110001

001011

010110


V5




V3

V2

V6

V4

V1

Раскраска графа

Задача: раскрасить вершины графа так, чтобы любые две смежные вершины были раскрашены в разные цвета, при этом число использованных цветов должно быть наименьшим.

Определение 30. Наименьшее возможное число раскраски графа называют его хроматическим числом.

Теорема. Граф является 2-хроматичным тогда и только тогда, когда он не содержит циклов.
1   2   3   4

Похожие:

Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой icon Сергей Николаевич Бердышев Технологии работы с клиентами разной трудности
Пособие содержит большое количество кейсов, с помощью которых легко понять особенности работы с различными заказчиками. Книга рассчитана...
Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой icon Наркотическая угроза: знать, чтобы выжить!
Теперь совершенно очевидно, что она характерна не только для стран Западного мира. Этим злом оказались поражены народы всех континентов...
Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой icon Методические указания по написанию контрольных работ 26 Ким для аттестации остаточных знаний 28
Учебно-методическое пособие предназначено для студентов направления: 080100, 080200, 100100, 100400, 230400, 072500
Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой icon Международные валютные отношения и валютный рынок Методическое пособие
Методическое пособие предназначено для студентов, обучающихся по специальности «Финансы и кредит» заочной формы обучения
Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой icon Учебно-методическое пособие для студентов Нижний Новгород 2009
Темперамент, Характер. Воля: Учебно-методическое пособие для студентов. Н. Новгород: нгпу, 2009. 42с
Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой icon Учебно-методическое пособие для проведения практических занятий для...
Методы научных исследований: учебно-методическое пособие для проведения практических
Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой icon Учебно-методическое пособие Н. Новгород
...
Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой icon Учебно-методическое пособие для студентов специальностей «История»
Шинаков Е. А., Поляков Г. П., Чубур А. А. Основы восточноевропейской археологии (учебно-методическое пособие). – Брянск, рио бгу,...
Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой icon И самостоятельной работы студентов
Учебное пособие предназначено для студентов Волжского государственного инженерно-педагогического университета, обучающихся по специальности...
Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой icon Учебное пособие Текст предоставлен правообладателем Логопатопсихология:...
«Логопатопсихология: учеб пособие для студентов / под ред. Р. И. Лалаевой, С. Н. Шаховской.»: Гуманитарный издательский центр владос;...
Литература


При копировании материала укажите ссылку © 2015
контакты
literature-edu.ru
Поиск на сайте

Главная страница  Литература  Доклады  Рефераты  Курсовая работа  Лекции