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

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

Ключевые слова:

графический объект
компьютерная графика
растровая графика
векторная графика
форматы графических файлов

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

3.2.1. Сферы применения компьютерной графики

Компьютерная графика прочно вошла в нашу повседневную жизнь. Она применяется:

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

Примеры компьютерной графики показаны на рис. 3.5.

Рис. 3.5.
Примеры компьютерной графики

http://snowflakes.barkleyus.com/ - с помощью компьютерных инструментов вы можете «вырезать» любую снежинку;
http://www.pimptheface.com/create/ - можно создать лицо, пользуясь большой библиотекой губ, глаз, бровей, причёсок и других фрагментов;
http://www.ikea.com/ms_RU/rooms_ideas/yoth/index.html - попробуйте подобрать новую мебель и отделочные материалы для своей комнаты.

3.2.2. Способы создания цифровых графических объектов

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

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

Существует несколько способов получения цифровых графических объектов.

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

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

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

Размеры пикселя зависят от разрешающей способности сканера, которая обычно выражается в dpi (dot per inch - точек на дюйм 1) и задаётся парой чисел (например, 600 х 1200 dpi). Первое число - это количество пикселей, которые могут быть выделены сканером в строке изображения длиной в 1 дюйм. Второе число - количество строк, на которые может быть разбита полоска изображения высотой в 1 дюйм.

1 Дюйм - единица длины в английской системе мер, равна 2,54 см.

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

Решение . Размеры сканируемого изображения составляют приблизительно 4x4 дюйма. С учётом разрешающей способности сканера всё изображение будет разбито на 4 4 1200 1200 пикселей.

Ответ: приблизительно 66 Мбайт.

Рекомендуем вам посмотреть анимации «Сканеры: общие принципы работы», «Сканеры: планшетный сканер», размещённые в Единой коллекции цифровых образовательных ресурсов (http://school-collection.edu.ru/). Эти ресурсы помогут вам более полно представить, как происходит процесс сканирования. Ресурс «Цифровая фотокамера» проиллюстрирует, как получаются цифровые фотографии (рис. 3.6).

Рис. 3.6.
Планшетный сканер и цифровая фотокамера

3.2.3. Растровая и векторная графика

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

Растровая графика

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

Качество растрового изображения возрастает с увеличением количества пикселей в изображении и количества цветов в палитре. При этом возрастает и информационный объём всего изображения. Большой информационный объём - один из основных недостатков растровых изображений.

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

Рис. 3.7.
Растровое изображение и его увеличенный фрагмент

Растровые графические изображения редко создают вручную. Чаще всего их получают путём сканирования подготовленных художниками иллюстраций или фотографий; в последнее время для ввода растровых изображений в компьютер широко применяются цифровые фотокамеры.

Векторная графика

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

Рис. 3.8.
Изображение из окружностей, отрезков и прямоугольника

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

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

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

Рис. 3.9.
Векторное изображение, его преобразованный фрагмент и простейшие геометрические фигуры, из которых «собран» этот фрагмент

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

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

Рис. 3.10.
Фрактальная графика

Более полную информацию по этому вопросу вы сможете найти в Интернете (например, по адресу http://ru.wikipedia.org/wiki/Фрактал).

3.2.4. Форматы графических файлов

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

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

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

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

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

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

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

2 Процесс открытия файла в программе, в которой он не был создан.

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

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

Решение .

Ответ: 9 Мб.

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

Решение .

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

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

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

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

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

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

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

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

Что такое компьютерная графика?
Перечислите основные сферы применения компьютерной графики.
Каким образом могут быть получены цифровые графические объекты?
Сканируется цветное изображение размером 10 х 15 см. Разрешающая способность сканера 600 х 600 dpi, глубина цвета - 3 байта. Какой информационный объём будет иметь полученный графический файл?
В чём разница между растровым и векторным способами представления изображения?
Почему считается, что растровые изображения очень точно передают цвет?
Какая операция по преобразованию растрового изображения ведёт к наибольшим потерям его качества - уменьшение или увеличение? Как вы можете это объяснить?
Почему масштабирование не влияет на качество векторных изображений?
Чем вы можете объяснить разнообразие форматов графических файлов?
В чём основное различие универсальных графических форматов и собственных форматов графических приложений?
Постройте как можно более полный граф для понятий п. 3.2.4.
Дайте развёрнутую характеристику растровых и векторных изображений, указав в ней следующее:
Рисунок размером 1024 х 512 пикселей сохранили в виде несжатого файла размером 1,5 Мб. Какое количество информации было использовано для кодирования цвета пикселя? Каково максимально возможное число цветов в палитре, соответствующей такой глубине цвета?
Несжатое растровое изображение размером 256 х 128 пикселей занимает 16 Кб памяти. Каково максимально возможное число цветов в палитре изображения?

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

Универсальным растровым графическим форматом является формат 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 цвета — чёрный и белый.

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

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

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

Теория графов берет начало с решения задачи о кенигсбергских мостах в 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-мерные двоичные наборы. Рёбра соединяют вершины, отличающиеся одной координатой.

Пример:

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

Первая и главная цель, которую нужно преследовать при изучении графов, –научить школьников видеть граф в условии задачи и грамотно переводить условие на язык теории графов. Не стоят рассказывать обе всем на нескольких занятиях подряд. Лучше разнести занятия по времени на 2–3 учебных года. (Прилагается разработка занятия “Понятие графа. Применение графов к решению задач” в 6 классе).

2. Теоретический материал к теме “Графы”.

Введение

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

Понятие графа

Рассмотрим две задачи.

Задача 1. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса?

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

Теперь сразу видно, что долететь с Земли до Марса нельзя.

Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4x4 убрать угловые клетки.

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

Решение: Занумеруем последовательно клетки доски:

А теперь с помощью рисунка покажем, что такой обход таблицы, как указано в условии, возможен:

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

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

Другое замечание касается вида графа. Попробуйте проверить, что граф для одной и той же задачи можно нарисовать разными способами; и наоборот для разных задач можно нарисовать одинаковые по виду графы. Здесь важно лишь то, какие вершины соединены друг с другом, а какие – нет. Например, граф для задачи 1 можно нарисовать по-другому:

Такие одинаковые, но по-разному нарисованные графы, называются изоморфными .

Степени вершин и подсчет числа ребер графа

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

С понятием степени вершины связана одна из основных теорем теории графов –теорема о честности числа нечетных вершин. Докажем ее мы немного позднее, а сначала для иллюстрации рассмотрим задачу.

Задача 3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа – 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится разным . Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным.

Ответ. Соединить телефоны таким образом невозможно.

Теорема : Любой граф содержит четное число нечетных вершин.

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

Связность графа

Есть еще одно важное понятие, относящееся к графам – понятие связности.

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

Задача 4. В стране Семерка 15 городов, каждый из городов соединен дорогами не менее, чем с семью другими. Докажите, что из каждого города модно добраться в любой другой.

Доказательство : Рассмотрим два произвольных А и В города и допустим, что между ними нет пути. Каждый из них соединен дорогами не менее, чем с семью другими, причем нет такого города, который был бы соединен с обоими рассматриваемыми городами (в противном случае существовал бы путь из A в B). Нарисуем часть графа, соответствующую этим городам:

Теперь явно видно, что мы получили не менее различных 16 городов, что противоречит условию задачи. Значит утверждение доказано от противного.

Если принять во внимание предыдущее определение, то утверждение задачи можно переформулировать и по-другому: “Доказать, что граф дорог страны Семерка связен.”

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

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

Задача 5 . В Тридевятом царстве только один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов, – по 20. Докажите, что из столицы можно долететь в город Дальний.

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

Графы Эйлера

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

Задача 6. Можно ли нарисовать изображенный на рисунке граф не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз?

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

Сейчас мы доказали теорему об Эйлеровых графах:

Теорема : Эйлеров граф должен иметь не более двух нечетных вершин.

И в заключение – задача о Кенигсбергских мостах.

Задача 7. На рисунке изображена схема мостов города Кенигсберга.

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

3. Задачи к теме “Графы”

Понятие графа.

1. На квадратной доске 3x3 расставлены 4 коня так, как показано на рис.1. Можно ли сделав несколько ходов конями, переставить их в положение, показанное на рис.2?

Рис. 1

Рис. 2

Решение. Занумеруем клетки доски, как показано на рисунке:

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

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

2. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3. Можно ли долететь по воздуху из города 1 в город 9 ?

Решение. Поставив в соответствие каждому городу точку и соединив точки линией, если сумма цифр делится на 3, получим граф, в котором цифры 3, 5, 9 связаны между собой, но не связаны с остальными. Значит долететь из города 1 в город 9 нельзя.

Степени вершин и подсчет числа ребер.

3. В государстве 100 городов к из каждого города выходит 4 дороги. Сколько всего дорог в государстве.

Решение. Подсчитаем общее количество выходящих городов дорог – 100 . 4 = 400. Однако при таком подсчете каждая дорога посчитана 2 раза – она выходит из одного города и входит в другой. Значит всего дорог в два раза меньше, т.е. 200.

4. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 – по 4 друга, а 10 – по 5 друзей?

Ответ. Нет (теорема о четности числа нечетных вершин).

5. У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей?

Ответ. Нет, не может.

6. Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?

Решение . Подсчитаем число городов. Число дорог равно числу городов х, умноженному на 3 (число выходящих из каждого города дорог) и разделенному на 2 (см. задачу 3). Тогда 100 = Зх/2 => Зх=200, чего не может быть при натуральном х. Значит 100 дорог в таком государстве быть не может.

7. Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.

Доказательство непосредственно следует из теоремы о четности числа нечетных вершин графа.

Связность.

8. В стране из каждого города выходит 100 дорог и из каждого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь из любого города можно добраться до любого другого.

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

Графы Эйлера.

9. Имеется группа островов, соединенных мостами так, что от каждого острова можно добраться до любого другого. Турист обошел все острова, пройдя по каждому мосту розно 1 раз. На острове Троекратном он побывал трижды. Сколько мостов ведет с Троекратного, если турист

а) не с него начал и не на нем закончил?
б) с него начал, но не на нем закончил?
в) с него начал и на нем закончил?

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

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

Существуют некоторые специальные графы, в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 вместе составляют полный граф.