Граф (неориентированный граф): различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером Это --- пример.)
 
Нет описания правки
 
(не показано 15 промежуточных версий 3 участников)
Строка 1: Строка 1:
Это --- пример.
'''Граф (неориентированный граф)''' (''[[Graph (undirected graph)]]'') — это
 
 
''' 1.''' Пара <math>(V,E)</math>, где <math>V</math> — непустое множество объектов
некоторой природы, называемых [[Вершина|''вершинами'']] графа, а <math>E</math> —
подмножество двухэлементных подмножеств множества <math>V</math>, называемых
[[Ребро|''ребрами'']] графа. Множества вершин и ребер графа <math>G</math> обозначают
<math>V(G)</math> и <math>E(G)</math> соответственно. Если <math>|V(G)| = n</math> и <math>|E(G)| = m</math>,
то говорят о <math>(n,m)</math>-графе <math>G</math>.
 
'''2.''' Пара <math>(V,E)</math>, где <math>V</math> —
множество [[Вершина|''вершин'']] графа, а <math>E</math> — множество [[Ребро|''ребер'']] —
есть подмножество множества <math>V_{-}^{2} / \sim</math> классов
эквивалентности, на которые множество <math>V_{-}^{2} = \{(v,w) | v
\neq w \}</math> разбивается отношением эквивалентности:
<math>(v_{1},w_{1}) \sim (v_{2},w_{2}) \Leftrightarrow (v_{1},w_{1}) =
(v_{2},w_{2})</math> или <math>(v_{1},w_{1}) = (w_{2},v_{2}).</math>
 
[[Файл:Graph.png|800px]]
 
'''3.''' Тройка <math>(V,E,P)</math>, где <math>V</math> — множество [[Вершина|''вершин'']], <math>E</math>
— множество объектов некоторой природы, отличной от природы
вершин, называемых [[Ребро|''ребрами'']], <math>P</math> — ''инцидентор'',
сопоставляющий с каждым ребром <math>e \in E</math> пару ''граничных вершин''
<math>v</math> и <math>w</math> из <math>V</math>.
 
'''4.''' Общее название как для
[[Неориентированный граф|неориентированного]], так  и  для  [[Ориентированный граф|ориентированного графов]].
 
== См. также ==
 
* [[Абстрактный граф]],
* [[Альфа-Перестановочный граф|Альфа-перестановочный граф]],
* [[Антисимметрический граф]],
* [[Аранжируемый граф]],
* [[Асимметричный граф]],
* [[Бесконечный граф]],
* [[Бесконтурный орграф]],
* [[Бихроматический граф]],
* [[Вершинно-критический граф]],
* [[Вершинно-непересекающиеся графы (подграфы)|Вершинно непересекающиеся графы]],
* [[K-Вершинно-связный граф|K-вершинно-связный граф]],
* [[Вершинно-симметрический граф]],
* [[Взаимно связный граф]],
* [[Взвешенный граф]],
* [[Внешнепланарный граф]],
* [[Внешнеплоский граф]],
* [[Вполне несвязный граф]],
* [[Выпуклый прямолинейный граф]],
* [[Гамильтонов граф]],
* [[Гамильтоново-связный граф]],
* [[Геодезический граф]],
* [[L-Геодезический граф|L-геодезический граф]],
* [[Геометрически двойственный граф]],
* [[Гипогамильтоновый граф]],
* [[Гомеоморфные графы]],
* [[Графы Куратовского]],
* [[Дважды хордальный граф]],
* [[Двойственно хордальный граф]],
* [[Двойственный граф]],
* [[Двудольный граф]],
* [[Двусторонний граф]],
* [[Дистанционно наследуемый граф]],
* [[Дистанционно-транзитивный граф]],
* [[K-Дольный граф|K-дольный граф]],
* [[Звездно-экстремальный граф]],
* [[Звездный граф]],
* [[N-Звездный граф|N-звездный граф]],
* [[Знаковый помеченный граф]],
* [[Изоморфные графы]],
* [[Индифферентный граф]],
* [[Индуктивный граф]],
* [[Информационный граф]],
* [[Конечный граф]],
* [[Г-Конечный граф|Гамма-конечный граф]],
* [[Корневой граф]],
* [[Коспектральные графы]],
* [[Критический граф]],
* [[Кубический граф]],
* [[Локально конечный граф]],
* [[Локально ограниченный граф]],
* [[Локально счетный граф]],
* [[Максимальный сильно сингулярный граф]],
* [[Максимальный сингулярный граф]],
* [[Минимально связный граф]],
* [[Многоугольный граф]],
* [[Накрывающий граф]],
* [[K-Насыщенный граф|K-насыщенный граф]],
* [[Неразделимый граф]],
* [[Неразложимый граф]],
* [[Несводимый граф]],
* [[Несепарабельный граф]],
* [[Нечетный граф]],
* [[Обратный орграф]],
* [[Общий граф]],
* [[Обыкновенный граф]],
* [[Однозначно раскрашиваемый граф]],
* [[Однородный граф]],
* [[Односторонне связный орграф]],
* [[Односторонний орграф]],
* [[Одноциклический граф]],
* [[Ориентированно-циклически замкнутый граф]],
* [[Ориентированный граф]],
* [[Ориентируемый граф]],
* [[Панциклический граф]],
* [[J-Панциклический граф|J-панциклический граф]],
* [[Планарный граф]],
* [[Плоский граф]],
* [[(a,b)-Плоский граф|(a,b)-плоский граф]],
* [[Покрывающий граф]],
* [[Полный граф]],
* [[Полный двудольный граф]],
* [[Полный k-дольный граф]],
* [[Полугамильтонов граф]],
* [[Полунесводимый граф]],
* [[Полуэйлеров граф]],
* [[Помеченный граф]],
* [[Пороговый граф]],
* [[Почти однородный граф]],
* [[Правильный граф]],
* [[Предельный граф]],
* [[Префиксный граф ширины n]],
* [[Прогрессивно конечный граф]],
* [[Прогрессивно ограниченный граф]],
* [[Производный граф]],
* [[Произвольно вычерчиваемый граф]],
* [[Произвольно гамильтонов граф]],
* [[Произвольно проходимый граф]],
* [[Простой граф]],
* [[Прямоугольный граф]],
* [[Псевдосимметрический граф]],
* [[Пустой граф]],
* [[Разборный граф]],
* [[Раскрашенный граф]],
* [[Реберно раскрашиваемый граф]],
* [[K-Раскрашенный граф|K-раскрашенный граф]],
* [[K-Раскрашиваемый граф|K-раскрашиваемый граф]],
* [[Расщепляемый граф]],
* [[Реберно-критический граф]],
* [[Реберно  k-раскрашиваемый граф]],
* [[Расширенный нечетный граф]],
* [[Реберно изоморфные графы]],
* [[Реберно-регулярный граф]],
* [[K-Реберно-связный граф|K-реберно-связный граф]],
* [[Реберно-симметрический граф]],
* [[Реберный граф]],
* [[Регрессивно конечный граф]],
* [[Регрессивно ограниченный граф]],
* [[Регуляризуемый граф]],
* [[Регулярный граф]],
* [[Регулярный степени 0 граф]],
* [[Реконструируемый граф]],
* [[Самодополнительный граф]],
* [[Самонегативный граф]],
* [[Сбалансированный граф]],
* [[Сводимый граф]],
* [[Связный граф]],
* [[K-Связный граф|K-связный граф]],
* [[2-Секционный граф|Два-секционный граф]],
* [[Сильно ориентированно-циклически замкнутый граф]],
* [[Сильно ориентированно-циклически-реберный граф]],
* [[Сильно связный граф]],
* [[Сильно-циклически замкнутый граф]],
* [[Сильно-циклически связный граф]],
* [[Симметрический граф]],
* [[Сингулярно связные графы]],
* [[Слабо связный граф]],
* [[Слабый орграф]],
* [[Смешанный граф]],
* [[Совершенный граф]],
* [[Соединяющий граф]],
* [[Соотнесенный неориентированный граф]],
* [[Составной граф]],
* [[Степенно-хордальный граф]],
* [[Строго геодезический граф]],
* [[Строго хордальный граф]],
* [[Структурный граф]],
* [[Стягиваемый граф]],
* [[Счетный граф]],
* [[Топологический граф]],
* [[S-Топологический граф|S-топологический граф]],
* [[Тороидальный граф]],
* [[Тотальный граф]],
* [[Транзитивно ориентируемый граф]],
* [[Транзитивный граф]],
* [[K-Транзитивный граф|K-транзитивный граф]],
* [[Триангулированный граф]],
* [[Тривиальный граф]],
* [[Узловой граф]],
* [[Унитарный граф]],
* [[K-Унитранзитивный граф|K-унитранзитивный граф]],
* [[Унициклический граф]],
* [[Упорядоченный граф]],
* [[Управляющий граф]],
* [[Хордальный граф]],
* [[Хордальный двудольный граф]],
* [[K-Хроматический граф|K-хроматический граф]],
* [[Цветной граф Кэлли]],
* [[Циклически жесткий граф]],
* [[Циклически замкнутый граф]],
* [[Циклически изоморфные графы]],
* [[Циклический граф]],
* [[Циркулянтный граф]],
* [[Частичный граф]],
* [[Четный граф]],
* [[Эйлеров граф]].
 
==Литература==
 
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.
 
 
[[Категория:Неориентированные графы]]

Текущая версия от 14:14, 24 декабря 2010

Граф (неориентированный граф) (Graph (undirected graph)) — это


1. Пара [math]\displaystyle{ (V,E) }[/math], где [math]\displaystyle{ V }[/math] — непустое множество объектов некоторой природы, называемых вершинами графа, а [math]\displaystyle{ E }[/math] — подмножество двухэлементных подмножеств множества [math]\displaystyle{ V }[/math], называемых ребрами графа. Множества вершин и ребер графа [math]\displaystyle{ G }[/math] обозначают [math]\displaystyle{ V(G) }[/math] и [math]\displaystyle{ E(G) }[/math] соответственно. Если [math]\displaystyle{ |V(G)| = n }[/math] и [math]\displaystyle{ |E(G)| = m }[/math], то говорят о [math]\displaystyle{ (n,m) }[/math]-графе [math]\displaystyle{ G }[/math].

2. Пара [math]\displaystyle{ (V,E) }[/math], где [math]\displaystyle{ V }[/math] — множество вершин графа, а [math]\displaystyle{ E }[/math] — множество ребер — есть подмножество множества [math]\displaystyle{ V_{-}^{2} / \sim }[/math] классов эквивалентности, на которые множество [math]\displaystyle{ V_{-}^{2} = \{(v,w) | v \neq w \} }[/math] разбивается отношением эквивалентности: [math]\displaystyle{ (v_{1},w_{1}) \sim (v_{2},w_{2}) \Leftrightarrow (v_{1},w_{1}) = (v_{2},w_{2}) }[/math] или [math]\displaystyle{ (v_{1},w_{1}) = (w_{2},v_{2}). }[/math]

Graph.png

3. Тройка [math]\displaystyle{ (V,E,P) }[/math], где [math]\displaystyle{ V }[/math] — множество вершин, [math]\displaystyle{ E }[/math] — множество объектов некоторой природы, отличной от природы вершин, называемых ребрами, [math]\displaystyle{ P }[/math]инцидентор, сопоставляющий с каждым ребром [math]\displaystyle{ e \in E }[/math] пару граничных вершин [math]\displaystyle{ v }[/math] и [math]\displaystyle{ w }[/math] из [math]\displaystyle{ V }[/math].

4. Общее название как для неориентированного, так и для ориентированного графов.

См. также

Литература

  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.