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

Определения. Графом G(V,E) называется совокупность двух множеств - непустого множества V (множества вершин) и множества Е неупорядоченных пар различных элемен­тов

Читайте также:
  1. I. Открытые способы определения поставщика.
  2. III. Используемые определения и обозначения
  3. Алгоритм определения предпочтительной организационной структуры управления диверсифицированной фирмы
  4. АНКЕТА ОПРЕДЕЛЕНИЯ ВОЛЕВЫХ КАЧЕСТВ У УЧАЩИХСЯ 12-16 ЛЕТ
  5. АНКЕТА ОПРЕДЕЛЕНИЯ ВОЛЕВЫХ КАЧЕСТВ У УЧАЩИХСЯ 16 ЛЕТ И СТАРШЕ И СТУДЕНТОВ
  6. АНКЕТА ОПРЕДЕЛЕНИЯ ВОЛЕВЫХ КАЧЕСТВ У УЧАЩИХСЯ 7-12 ЛЕТ
  7. Базовые параметры радиационных свойств горных пород и методы их определения
  8. Базовые параметры электромагнитных свойств горных пород и методы их определения.
  9. Бальнеология. Понятия и определения
  10. БИАС-тест определения репрезентативных систем
  11. Более результативной с точки зрения определения победите-
  12. Верный способ определения ГПЗ зоны в помещении

Графом G(V,E) называется совокупность двух множеств - непустого множества V (множества вершин) и множества Е неупорядоченных пар различных элемен­тов множества V (Е - множество ребер).

G(V,E): , E VxV.

Число вершин графа G обозначим р, а число ребер – q.

р(G) = |V| q(G) = |E|.

Часто рассматриваются следующие родственные графам объекты.

1. Если элементами множества Е являются упорядоченные пары, то граф назы­вается ориентированным (илиорграфом). В этом случае элементы множества V называются узлами, а элементы множества - дугами (G(V, )).

2. Если элементом множества Е может быть пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлей, а граф назы­вается графом с петлями (или псевдографом).

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

Далее выражение: граф G(V,E) означает неориентированный граф без петель и кратных ребер.

Обычно граф изображают диаграммой: вершины - точками (или кружками), ребра - линиями.

Примеры.

1. . .

 
 


Т.о. это неориентированный граф с петлей и кратными ребрами.

Рис. 3.3. Неориентированный граф с петлей и кратными ребрами.

2. . .

Т.о. это ориентированный граф с петлей и кратными ребрами.

 
 


Рис. 3.4. Ориентированный граф с петлей и кратными ребрами.

 
 


3. . , т.о.

Рис. 3.5. Неориентированный граф с петлей.

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |


Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)