Инструменты пользователя

Инструменты сайта


examination:diskretka:question2

Вопрос №2. Понятие графа, подграфа. Гомоморфизмы графов. Изоморфные графы. Геометрическое представление графов.

ВАЖНО!
Для адекватного просмотра больших картинок через Opera Mini нужно:
1) залезть в параметры
2) поставить качество изображений на «высокое»
3) убрать галочку с «мобильный вид»
4) сохранить и перезагрузить страницу

Общее понятие графа

тройка Г=(V,E,I) называется с множеством вершин V, множеством ребер E, отношением инцедентности I.

Гомоморфизм графа в граф

{{:examination:diskretka:screenshot074.png|

1.Композиция гомоморфизмов

2.Наличие тождественногогомоморфизма

Взаимнообратные гомоморфизмы

Гомоморфизм, имеющий обратный, называется изоморфизмом

(Г изоморфно Г')

Свойства

  1. Композиция изоморфизмов есть изоморфизм
  2. Тождественный изоморфизм есть изоморфизм
  3. Гомоморфизм обратный изоморфизму есть изоморфизм

Г и Г' называются изоморфными, если существует изоморфизм Г на Г' :

Следствие

«Отношение» изоморфности графов обладает следующими свойствами:

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

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

- это представление его фигурой определенного вида.

В качестве пространства, в котором располагается упомянутая фигура, обычно выбирается Евклидово пространство R^n подходящей размерности n.

На практике n=2 (плоское представление графа) или n=3 (пространственное представление графа).

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

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

Перейдем к точному описанию понятия геометрической модели графа :

1. Множество вершин графа изображается множеством соответствующих точек на плоскости или пространстве.

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

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

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

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

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

Замечание 1 Понятие непрерывная линия является известным.

Замечание 2 Рекомендуется выбирать не просто непрерывные линии, а линии гладкие.

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

Замечание 4 последнее, что нужно сделат с линиями, это указать их оиентацию, т.е направление движения вдол линии.

Определим понятия ориентированного ребра и петли:

Пусть для тройки

1).

В этом случае ребро e называется ориентированным ребром или дугой, вершина v называетсся началом дуги e, вершина w - концом.

2).

В этом случае е называется неориентированным ребром, или ребром в узком смысле, w и v являются одновременно и началом, и концом.

Неориентированное ребро не то же самое, что

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

3).

В этом случае е называется петлей, v - начало и конец.

examination/diskretka/question2.txt · Последние изменения: 2014/01/15 12:14 (внешнее изменение)