Постройте как можно более полный граф. Графы

1736 год, г.Кёнигсберг. Через город протекает река Прегеля. В городе - семь мостов, расположенных так, как показано на рисунке выше. С давних времен жители Кенигсберга бились над загадкой: можно ли пройти по всем мостам, пройдя по каждому только один раз? Эту задачу решали и теоретически, на бумаге, и на практике, на прогулках - проходя по этим самым мостам. Никому не удавалось доказать, что это неосуществимо, но и совершить такую «загадочную» прогулку по мостам никто не мог.

Разрешить проблему удалось знаменитому математику Леонарду Эйлеру. Причем, он решил не только эту конкретную задачу, но придумал общий метод решения подобных задач. При решении задачи о Кенигсбергских мостах Эйлер поступил следующим образом: он "сжал" сушу в точки, а мосты "вытянул" в линии. Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют ГРАФОМ .

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

Виды графов:

1. Ориентированный граф (кратко орграф ) - рёбрам которого присвоено направление.

2. Неориентированный граф - это граф , в котором нет направления линий.

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

Решение задач с помощью графов:

Задача 1.

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

Задача 2.

На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому.

Решение:

Вершины графа - это деревья, обозначенный первой буквой названия дерева. В данной задача два отношения: “быть ниже” и “быть выше”. Рассмотрим отношение “быть ниже” и проведем стрелки от более низкого дерева к более высокому. Если в задаче сказано, что рябина выше лиственницы, то стрелку ставим от лиственницы к рябине и т.д. Получаем граф, на котором видно, что самое низкое дерево – клен, затем идут яблоня, лиственница, рябина, сосна, дуб, береза и тополь.

Задача 3.

У Наташи есть 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо?

Решение:

Ниже представлен разбор задач.

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

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

Универсальным растровым графическим форматом является формат ВМР. Графические файлы в этом формате имеют большой информационный объём, так как в них на хранение информации о цвете каждого пикселя отводится 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 Кб памяти. Каково максимально возможное число цветов в палитре изображения?

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

Базовые определения

Из чего состоит граф в информатике? Он включает множество объектов, называемых вершинами или узлами, некоторые пары которых связаны т. н. ребрами. Например, граф на рисунке (а) состоит из четырех узлов, обозначенных А, В, С, и D, из которых B соединен с каждой из трех других вершин ребрами, а C и D также соединены. Два узла являются соседними, если они соединены ребром. На рисунке показан типичный способ того, как строить графы по информатике. Круги представляют вершины, а линии, соединяющие каждую их пару, являются ребрами.

Какой граф называется неориентированным в информатике? У него отношения между двумя концами ребра являются симметричными. Ребро просто соединяет их друг с другом. Во многих случаях, однако, необходимо выразить асимметричные отношения - например, то, что A указывает на B, но не наоборот. Этой цели служит определение графа в информатике, по-прежнему состоящего из набора узлов вместе с набором ориентированных ребер. Каждое ориентированное ребро представляет собой связь между вершинами, направление которой имеет значение. Направленные графы изображают так, как показано на рисунке (b), ребра их представлены стрелками. Когда требуется подчеркнуть, что граф ненаправленный, его называют неориентированным.

Модели сетей

Графы в информатике служат сетевых структур. На следующем рисунке представлена структура интернета, тогда носившего название ARPANET, в декабре 1970 года, когда она имела лишь 13 точек. Узлы представляют собой вычислительные центры, а ребра соединяют две вершины с прямой связью между ними. Если не обращать внимания на наложенную карту США, остальная часть изображения является 13-узловым графом, подобным предыдущим. При этом действительное расположение вершин несущественно. Важно, какие узлы соединены друг с другом.

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

Маршруты

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

Эта идея мотивирует определение маршрута как последовательности вершин, связанных между собой ребрами. Иногда возникает необходимость рассматривать маршрут, содержащий не только узлы, но и последовательность ребер, их соединяющих. Например, последовательность вершин MIT, BBN, RAND, UCLA является маршрутом в графе интернета ARPANET. Прохождение узлов и ребер может быть повторным. Например, SRI, STAN, UCLA, SRI, UTAH, MIT также является маршрутом. Путь, в котором ребра не повторяются, называется цепью. Если же не повторяются узлы, то он носит название простой цепи.

Циклы

Особенно важные виды графов в информатике - это циклы, которые представляют собой кольцевую структуру, такую как последовательность узлов LINC, CASE, CARN, HARV, BBN, MIT, LINC. Маршруты с, по крайней мере, тремя ребрами, у которых первый и последний узел одинаковы, а остальные различны, представляют собой циклические графы в информатике.

SRI, STAN, UCLA, SRI является самым коротким, а SRI, STAN, UCLA, RAND, BBN, UTAH, SRI значительно больше.

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

Связный граф: определение (информатика)

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

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

Компоненты

Если графы в информатике не связаны, то они естественным образом распадаются на набор связанных фрагментов, групп узлов, которые являются изолированными и не пересекающимися. Например, на рисунке изображены три таких части: первая - А и В, вторая - C, D и Е, и третья состоит из оставшихся вершин.

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

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

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

Максимальная компонента

Существует метод качественной оценки компонентов связности. Например, есть всемирная социальная сеть со связями между двумя людьми, если они являются друзьями.

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

Глобальная сеть друзей

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

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

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

Катастрофа слияния компонент

Например, после прибытия европейских исследователей в цивилизации Западного полушария примерно полтысячелетия назад произошел глобальный катаклизм. С точки зрения сети это выглядело так: пять тысяч лет глобальная социальная сеть, вероятно, состояла из двух гигантских компонент - одной в Северной и Южной Америке, а другой - в Евразии. По этой причине технологии развивалась независимо в двух компонентах, и, что еще хуже, так же развивались и болезни человека и т. д. Когда две компоненты, наконец, вошли в контакт, технологии и заболевания одной быстро и катастрофически переполнили вторую.

Американская средняя школа

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

Расстояние и поиск в ширину

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

Для этого следует определить длину маршрута, равную числу шагов, которые он содержит от начала до конца, т. е. число ребер в последовательности, которая его составляет. Например, маршрут MIT, BBN, RAND, UCLA имеет длину 3, а MIT, UTAH - 1. Используя длину пути, можно говорить о том, расположены ли два узла в графе близко друг к другу или далеко: расстояние между двумя вершинами определяется как длина самого короткого пути между ними. Например, расстояние между LINC и SRI равно 3, хотя, чтобы убедиться в этом, следует удостовериться в отсутствии длины, равной 1 или 2, между ними.

Алгоритм поиска в ширину

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

Самым естественным способом это сделать и, следовательно, наиболее эффективным, является следующий (на примере глобальной сети друзей):

Все друзья объявляются находящимися на расстоянии 1.
Все друзья друзей (не считая уже отмеченных) объявляются находящимися на расстоянии 2.
Все их друзья (опять же, не считая помеченных людей) объявляются удаленными на расстояние 3.

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

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

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

Мир тесен

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

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

Теория «шести рукопожатий» впервые экспериментально исследовалась Стенли Милгрэмом и его коллегами в 1960-е годы. Не имея какого-либо набора данных социальных сетей и с бюджетом в 680 долларов он решил проверить популярную идею. С этой целью он попросил 296 случайно отобранных инициаторов попробовать отослать письмо биржевому брокеру, который жил в пригороде Бостона. Инициаторам были даны некоторые личные данные о цели (включая адрес и профессию), и они должны были переслать письмо лицу, которого они знали по имени, с теми же инструкциями, чтобы оно достигло цели как можно быстрее. Каждое письмо прошло через руки ряда друзей и образовало цепочку, замыкавшуюся на биржевом брокере за пределами Бостона.

Среди 64 цепочек, достигших цели, средняя длина равнялась шести, что подтвердило число, названное два десятилетия ранее в названии пьесы Джона Гэра.

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

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

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

Пример:

Понравилась статья? Поделитесь ей

Распечатать статью