Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Что такое граф?

Реферат

на тему:

«Планарные графы»

Выполнил: Винокуров Ю.А.,

Карпов В.С,

студенты гр.628-1

Проверил: Машеева Е.П.

Улан-Удэ

План:

1. Что такое граф..............................................................................................3

2. Общее определение планарного графа......................................................4

3. Формулы Эйлера..........................................................................................5

4. Теорема Куратовского.................................................................................8

5. Список использованной литературы.........................................................10

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

Что такое граф?

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

Существуют два основных вида графов (и множество их подвидов): ориентированные, в которых линии имеют направление от одной точки к другой, и неориентированные, в которых линии не имеют направления.

Общее определение планарного графа

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

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

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

На рисунке 1 показан планарный граф, изображенный так, что его ребра пересекаются, а на рисунке 2 показан тот же граф без пересечений ребер, т. е. плоский граф. Не всякий граф является планарным. Стандартным примером не планарного графа является граф К_3,3 (Рисунок 3), возникающей задаче «о трех домах и трех колодцах», в которой жители домов хотели бы ходить к любому колодцу так, чтобы их тропы не пересекались, т. е. чтобы никогда не встречать своих соседей. Для этого граф, соединяющий дома и колодцы, должен быть планарным. Однако он непланарен, так что эта задача не имеет решения. Другой важный пример не планарного графа – граф К₅ (Рисунок 4)