Постройте как можно более полный граф. Теория графов: основные понятия и задачи

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

Теория графов берет начало с решения задачи о кенигсбергских мостах в 1736 году знаменитым математиком Леонардом Эйлером (1707-1783: родился в Швейцарии, жил и работал в России).

Задача о кенигсбергских мостах.

В прусском городке Кенигсберг на реке Прегал семь мостов. Можно ли найти маршрут прогулки, который проходит ровно 1 раз по каждому из мостов и начинается и заканчивается в одном месте?

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

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

Задача о трех домах и трех колодцах.

Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались. Эта задача была решена (показано, что решения не существует) Куратовским (1896 – 1979) в 1930 году.

Задача о четырех красках. Разбиение плоскости на непересекающиеся области называется картой . Области карты называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом. С конца XIX века известна гипотеза, что для этого достаточно четырех красок. Гипотеза не доказана до сих пор.

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

Проверить «вручную» полученное решение невозможно – объем перебора выходит за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки…

Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они все сделали правильно.

Определение 7.1. Графом G = G (V , E ) называется совокупность двух конечных множеств: V – называемого множеством вершин и множества E пар элементов из V, т.е. EÍV´V, называемого множеством рёбер , если пары неупорядочены, или множеством дуг , если пары упорядочены.

В первом случае граф G (V , E ) называется неориентированным , во втором – ориентированным.

ПРИМЕР. Граф с множеством вершин V = {а,b,с} и множеством ребер Е ={{а, b}, {b, с}}

ПРИМЕР. Граф, у которого V = {a,b,c,d,e} и Е = {{а, b}, {а, е}, {b, е}, {b, d}, {b, с}, {с, d}},

Если e=(v 1 ,v 2), еÎЕ, то говорят, что ребро е соединяет вершины v 1 и v 2 .

Две вершины v 1 ,v 2 называются смежными , если существует соединяющее их ребро. В этой ситуации каждая из вершин называется инцидентной соответствующему ребру.

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

Число вершин графа G обозначим v , а число ребер - e :

Геометрическое представление графов следующее:

1) вершина графа – точка в пространстве (на плоскости);

2) ребро неориентированного графа – отрезок;

3) дуга ориентированного графа – направленный отрезок.

Определение 7.2. Если в ребре e=(v 1 ,v 2) имеет место v 1 =v 2 , то ребро е называется петлёй . Если в графе допускается наличие петель, то он называется графом с петлями или псевдографом .

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

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

Определение 7.3. Граф G  (V  , E  ) называется подграфом (или частью ) графа G (V ,E ), если V  V , E  E . Если V  = V , то G  называется остовным подграфом G .

Пример 7 . 1 . Дан неориентированный граф.

Определение 7.4. Граф называется полным , если любые две его вершины соединены ребром. Полный граф с n вершинами обозначается через K n .

Графы К 2 , К 3, К 4 и К 5 .

Определение 7.5. Граф G =G (V , E ) называется двудольным , если V можно представить как объединение непересекающихся множеств, скажем V =A B , так что каждое ребро имеет вид (v i , v j ), где v i A и v j B .

Каждое ребро связывает вершину из А с вершиной из В, но никакие две вершины из А или две вершины из В не являются связанными.

Двудольный граф называется полным двудольным графом K m , n , если A содержит m вершин, B содержит n вершин и для каждого v i A , v j B имеем (v i , v j )E .

Таким образом, для каждого v i A , и v j B имеется связывающее их ребро.

K 12 K 23 K 22 K 33

Пример 7 . 2 . Построить полный двудольный граф K 2,4 и полный граф K 4 .

Граф единичного n -мерного куба В n .

Вершины графа - n-мерные двоичные наборы. Рёбра соединяют вершины, отличающиеся одной координатой.

Пример:

Нуль-граф и полный граф.

Существуют некоторые специальные графы, вcтречающиеся во многих приложениях теории графов. Будем пока опять рассматривать граф как наглядную схему, иллюстрирующую ход спортивных состязаний. До начала сезона, пока еще никакие игры не проводились, на графе нет никаких ребер. Такой граф состоит из одних изолированных вершин, т.е. из вершин,соединенных никакими ребрами. Граф такого вида мы будем называть нуль-графом . На рис. 3 приведены такие графы для случаев, когда число команд, или вершин, равно 1, 2, 3, 4 и 5. Эти нуль-графы обычно обозначаются символами О1, О2, О3 и т.д., так что Оn-это нуль-граф с n вершинами, не имеющий ребер.

Рассмотрим другой крайний случай. Предположим, что по окончании сезона каждая команда сыграла по одному разу с каждой из осталыных команд. Тогда на соответствующем графе каждая пара вершин будет соединена ребром. Такой граф называется полным графом . На рис.4 изображены полные графы с числом вершин n = 1, 2, 3, 4, 5. Мы обозначаем эти полные графы соответственно через U1, U2, Uз,U4 и U5, так что граф Un состоит из 11 вершин и ребер, соединяющих всевозможные пары этих вершин. Этот граф можно представпять себе как n-угольник, в котором проведены все диагонали.

Имея некоторый граф, например граф G, изображенный на рис. 1, мы всегда можем превратить его в полный граф с теми же самыми вершинами, добавив недостающие ребра (т. е. ребра, соответствующие играм, которые только еще будут сыграны). На рис. 5 мы сделали это для графа рис. 1 (еще не состоявшиеся игры изображены пунктиром). Можно также отдельно начертить граф, соответствующий пока еще не сыгранным, будущим играм. Для графа G при этом получится граф, изображенный на рис. 6.

Этот новый граф мы называем дополнением графа G; принято обозначать его через G1. Взяв дополнение графа G1, мы снова получим граф G. Ребра обоих графов G1 и G вместе составляют полный граф.

Формат графического файла — это способ представления графических данных на внешнем носителе. Различают растровые и векторные форматы графических файлов, среди которых, в свою очередь, выделяют универсальные графические форматы и собственные (оригинальные) форматы графических приложений .

Универсальные графические форматы «понимаются» всеми приложениями, работающими с растровой (векторной) графикой.

Универсальным растровым графическим форматом является формат BMP . Графические файлы в этом формате имеют большой информационный объём, так как в них на хранение информации о цвете каждого пикселя отводится 24 бита.

В рисунках, сохранённых в универсальном растровом формате GIF , можно использовать только 256 разных цветов. Такая палитра подходит для простых иллюстраций и пиктограмм. Графические файлы этого формата имеют небольшой информационный объём. Это особенно важно для графики, используемой во Всемирной паутине, пользователям которой желательно, чтобы запрошенная ими информация появилась на экране как можно быстрее.

Универсальный растровый формат JPEG разработан специально для эффективного хранения изображений фотографического качества. Современные компьютеры обеспечивают воспроизведение более 16 миллионов цветов, большинство из которых человеческим глазом просто неразличимы. Формат JPEG позволяет отбросить «избыточное» для человеческого восприятия разнообразие цветов соседних пикселей. Часть исходной информации при этом теряется, но это обеспечивает уменьшение информационного объёма (сжатие) графического файла. Пользователю предоставляется возможность самому определять степень сжатия файла. Если сохраняемое изображение — фотография, которую предполагается распечатать на листе большого формата, то потери информации нежелательны. Если же этот фото — снимок будет размещён на Web-странице, то его можно смело сжимать в десятки раз: оставшейся информации будет достаточно для воспроизведения изображения на экране монитора.

К универсальным векторным графическим форматам относится формат WMF , используемый для хранения коллекции картинок Microsoft.

Универсальный формат EPS позволяет хранить информацию как о растровой, так и о векторной графике. Его часто используют для импорта файлов в программы подготовки полиграфической продукции.

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

Задача 1.
Для кодирования одного пикселя используется 3 байта. Фотографию размером 2048 х 1536 пикселей сохранили в виде несжатого файла. Определите размер получившегося файла.

Решение:
i = 3 байта
K= 2048 1536
I — ?

I=K i
I = 2048 1536 3 = 2 2 10 1,5 2 10 3 = 9 2 20 (байтов) = 9 (Мб).

Ответ: 9Мб.

Задача 2.
Несжатое растровое изображение размером 128 х 128 пикселей занимает 2 Кб памяти. Каково максимально возможное число цветов в палитре изображения?

Решение:
K = 128 128
I = 2 Кб
N -?

I=K i
i=I/K
N=2 i
i = (2 1024 8)/(128 128) = (2 2 10 2 3) /(2 7 2 7) = 2 1+10+3 /2 7+7 = 2 14 /2 14 = 1 (бит).
N = 2 1 = 2.

Ответ: 2 цвета — чёрный и белый.

Самое главное:

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

Теоретические сведения

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

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

число вершин с нечетной степенью у любого графа четно;
во всяком графе с п вершинами, где п > 2, всегда найдутся по меньшей мере две вершины с одинаковыми степенями;
если в графе с вершинами п > 2 в точности две вершины имеют одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина степени 0, либо в точности одна вершина степени (п - 1).

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

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

Х 5 (у /) = 2т ’

где т - количество вершин, а суммирование ведется по всем вершинам от 1 до п.

Задачи

Задача 2.42. Построить граф на восьми вершинах, имеющий следующее распределение степеней вершин: две вершины степени 4; три вершины степени 3; две вершины степени 2; одна вершина степени 1.

Решение.

Суммарная степень всех вершин равна 2-4 + 3- 3 + 2- 2+1 1=22, отсюда следует, что всего 11 ребер. Строить графы на основании вектора степеней проще, начиная с вершин больших степеней. Вер-

Таблица 2.9

Соответствие между описанием графа и его свойствами

Прилагательное	Числительное	Что это значит
		В графе ровно одна компонента связности
Несвязный		В графе более одной компоненты, его диаметр точно равен бесконечности
Регулярный	5(У;) = СОШІ	Степени всех вершин равны
Регулярный степени у	з(Уі)=У	Степени всех вершин равны у. Если известно п (число вершин), то можно сразу рассчитать т (число ребер): т-п? у/2 (п или у должно быть числом четным)
Ациклический	у= т-п + к = 0	Цикломатическое число равно нулю, в графе нет циклов, это - дерево или лес (в зависимости от связности), такие графы всегда можно раскрасить в два цвета. Если известны две переменные из трех (п , т, к), то с помощью формулы можно найти оставшуюся
Дерево(или ациклический связный граф)	у= т- п + 1 =0, откуда т- п - 1	Цикломатическое число равно нулю, в графе нет циклов, это - дерево, такие графы всегда можно раскрасить в два цвета. Если известна одна переменная из двух (п или т), то с помощью формулы можно найти вторую
Бихроматиче-		Хроматическое число графа равно двум, такие графы всегда можно раскрасить в два цвета, это - двудольные графы, графически это или ациклические графы, или графы, у которых все циклы имеют четную длину

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

Задача 2.43. Построить граф на шести вершинах, имеющий следующее распределение степеней вершин: две вершины степени 3;

Рис. 2.8.

две вершины степени 2; одна вершина степени 1; одна вершина имеет произвольную степень.

Решение.

Суммарная степень вершин равна 11, следовательно, оставшаяся вершина должна иметь нечетную степень, т.е. 1,3 или 5. Таким образом, возможно построить три разных графа (рис. 2.9).

Рис. 2.9.

Задача 2.44. Построить граф, имеющий следующий вектор степеней вершин: 5 = {1, 2, 2, 3, 4, 4, 5}.

Решение.

Суммарная степень равна 5 + 8 + 3 + 4+1=21. Так как это нечетное число, что противоречит теореме (количество ребер в два раза меньше этого числа, но 21 нацело на 2 не делится).

Ответ. Такого графа не существует.

Задача 2.45. Построить граф, имеющий следующий вектор степеней вершин: 5 = {1, 1,2, 2, 2, 4, 4, 4, 4}.

Задача 2.46. Построить граф, имеющий следующий вектор степеней вершин: 5 = {5, 5, 6, 6, 6, 6, 6}.

Задача 2.47. Построить граф, имеющий следующий вектор степеней вершин: 5 = {1, 1, 1,2, 3, 3, 3, 3, 5, 5, 5}.

Задача 2.48. Построить граф, имеющий следующий вектор степеней вершин: 5 = {3, 3, 3, 3, 3, 3, 3, 7}.

Задача 2.49. Построить граф на шести вершинах, имеющий следующее распределение степеней вершин: три вершины степени 5, а другие три вершины - неизвестной степени.

Задача 2.50. Построить граф на десяти вершинах, имеющий ребер в два раза больше, чем вершин, и следующее распределение степеней вершин: две вершины степени 6; четыре вершины степени 5; две вершины степени 4; две вершины произвольной степени - или обосновать невозможность построения такого графа.

Задача 2.51. Построить граф на десяти вершинах, имеющий следующее распределение степеней вершин: одна вершина степени 7; две вершины степени 6; две вершины степени 5; две вершины степени 4; две вершины степени 3; одна вершина степени 2 - или обосновать невозможность построения такого графа.

Задача 2.52. Построить граф на 11 вершинах, имеющий следующее распределение степеней вершин: одна вершина степени 7; две вершины степени 6; две вершины степени 5; две вершины степени 4; две вершины степени 3; одна вершина степени 2 - или обосновать невозможность построения такого графа.

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

Универсальным растровым графическим форматом является формат ВМР. Графические файлы в этом формате имеют большой информационный объём, так как в них на хранение информации о цвете каждого пикселя отводится 24 бита.

В рисунках, сохранённых в универсальном растровом формате GIF, можно использовать только 256 разных цветов. Такая палитра подходит для простых иллюстраций и пиктограмм. Графические файлы этого формата имеют небольшой информационный объём. Это особенно важно для графики, используемой во Всемирной паутине,

пользователям которой желательно, чтобы запрошенная ими информация появилась на экране как можно быстрее.

Универсальный растровый формат JPEG разработан специально для эффективного хранения изображений фотографического качест“ ва. Современные компьютеры обеспечивают воспроизведение более 16 миллионов цветов, большинство из которых человеческим глазом прост неразличимы. Формат JPEG позволяет отбросить «избыточное» для человеческого восприятия разнообразие цветов соседних пикселей. Часть исходной информации при этом теряется, но это обеспечивает уменьшение информационного объёма (сжатие) графического файла. Пользователю предоставляется возможность самому определять степень сжатия файла. Если сохраняемое изображение - фотография, которую предполагается распечатать на листе большого формата, то потери информации нежелательны. Если же этот фотоснимок будет размещён на ХЫеЬ-странице, то его можно смело сжимать в десятки раз: оставшейся информации будет достаточно для воспроизведения изображения на экране монитора.

К универсальным векторным графическим форматам относится формат WMF, используемый для хранения коллекции картинок Microsoft (http://office.microsoft.com/ru-ru/clipart).

Универсальный формат EPS позволяет хранить информацию как о растровой, так и о векторной графике. Его часто используют для импорта! файлов в программы подготовки полиграфической продукции.

Задача 1 . Для кодирования одного пикселя используется З байта. Фотографию размером 2048 х1536 пикселей сохранили в виде несжатого файла. Определите размер получившегося файла. Решение.

I-k.i i-I/k

i-2. 1024 8/(128. 128) =

2 2 10 2 3 /(2 7 2 7) = 2 1 + 10 + 3 /2 7 + 7 2 14 /2 14 = 1 (бит). ЛГ- 21-2.

Ответ: 2 цвета - чёрный и белый.

САМОЕ ГЛАВНОЕ

Компьютерная графика - это широкое понятие, обозначающее: 1) разные виды графических объектов, созданных или обработанных с помощью компьютеров; 2) область деятельности, в которой компьютеры используются как инструменты создания и обработки графических объектов.

В зависимости от способа создания графического изображения различают растровую и векторную графику.

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

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

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

а Вопросы и задания

1. Что такое компьютерная графика?

2. Перечислите основные сферы применения компьютерной графики.

З. Каким образом могут быть получены цифровые графические объекты?

4. Сканируется цветное изображение размером 10 х 15 см. Разрешающая способность сканера 600 х 600 dpi, глубина цвета - З байта. Какой информационный объём будет иметь полученный графический файл?

5. В чём разница между растровым и векторным способами представления изображения?

б. Почему считается, что растровые изображения очень точно передают цвет?

7. Какая операция по преобразованию растрового изображения ведёт к наибольшим потерям его качества - уменьшение или увеличение? Как вы можете это объяснить?

8. Почему масштабирование не влияет на качество векторных изображений?

9. Чем вы можете объяснить разнообразие форматов графических файлов?

Компьютерная графика

10. В чём основное различие универсальных графических форматов и собственных форматов графических приложений?

11. Постройте как можно более полный граф для понятий п. 3.2.4.

12. Дайте развёрнутую характеристику растровых и векторных изображений, указав в ней следующее:

а) из каких элементов строится изображение;

б) какая информация об изображении сохраняется во внешней памяти;

в) как определяется размер файла, содержащего графическое изображение;

г) как изменяется качество изображения при масштабировании;

д) каковы основные достоинства и недостатки растровых (векторных) изображений.

13. Рисунок размером 1024 х 512 пикселей сохранили в виде несжатого файла размером 1,5 Мб. Какое количество информации было использовано для кодирования цвета пикселя? Каково максимально возможное число цветов в палитре, соответствующей такой глубине цвета?

14. Несжатое растровое изображение размером 256 х 128 пикселей занимает 16 Кб памяти. Каково максимально возможное число цветов в палитре изображения?