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

Понятие графа, методы описания графа, виды графов. Эйлеровы и гамильтоновы графы.



Читайте также:
  1. I. Понятие о бинере и его роль в метафизике
  2. II. Методы и методики диагностики неосознаваемых побуждений.
  3. II.9. МЕТОДЫ АТОМНО-ЭМИССИОННОГО СПЕКТРАЛЬНОГО АНАЛИЗА
  4. V1: 02. Методы обследования в стоматологии
  5. V1: 12. Физические методы диагностики и лечения в стоматологии
  6. V1: 14. Методы обследования в челюстно-лицевой хирургии
  7. VI. Методы психодиагностики, их классификация.

Пусть X - произвольное непустое множество и Х Х - его декартов квадрат, т.е. множество всех упорядоченных пар (x1, x2)из элементов множества X. Если множество X - конечно и состоит из п элементов, то его декартов квадрат Х Х содержит п2 пар, и пары (x1, x2(x2, , x1) являются различными элементами множества Х Х при - Иногда множество Х Х называют упорядоченным произведением множества X на себя.

Рассмотрим теперь так называемое неупорядоченное произведение Х&Х множества X на себя, которое определяется как множество всех неупорядоченных пар из элементов множества X. Элементы из Х&Х будем обозначать (х12). Ясно, что во множестве Х&Х пары }2) и (х2 &x2) не различимы. Если множество X - конечно и состоит из п элементов, то множество Х&Х содержит элементов.

Графом G(V, E, f) называется совокупность непустого множества V, изолированного от него произвольного множества Е и отображения f:E—> V&V множества Е в V&V, которое каждому элементу из Е ставит в соответствие некоторый элемент из V&V. При этом множества V и Е называются соответственно множеством вершин и множеством ребер графа G(V, Е, f), а отображение f называется отображением инциденции этого графа.

часто вершины и ребра графа объединяются одним общим термином - элементы графа.

граф G это совокупность двух множеств: вершин V и ребер Е, между элементами которых определено отношение инцидентности - каждое ребро е Е инцидентно ровно двум вершинам v', v" V, которые оно соединяет. При этом вершина v' (v") и ребро е называются инцидентными друг другу, а вершины v' и v ", являющиеся для ребра е концевыми точками, называются смежными

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

Граф, содержащий направленные ребра (дуги) с началом v' и концом v", называется ориентированным (орграфом), а ненаправленные – неориентированным.

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

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

Граф называется конечным, если множество его элементов (вершин и ребер) конечно.

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

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

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

Локальной степенью (или просто степенью) вершины v V графа G называется количество ребер , инцидентных вершине v.


Дата добавления: 2015-07-11; просмотров: 102 | Нарушение авторских прав






mybiblioteka.su - 2015-2024 год. (0.005 сек.)