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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показана 1 промежуточная версия 1 участника)
Строка 1: Строка 1:
'''Граф (неориентированный граф)''' ([[Graph (undirected graph)]])--- это
'''Граф (неориентированный граф)''' (''[[Graph (undirected graph)]]'') это




''' 1.''' Пара <math>(V,E)</math>, где <math>V</math> --- непустое множество объектов
''' 1.''' Пара <math>(V,E)</math>, где <math>V</math> непустое множество объектов
некоторой природы, называемых [[Вершина|''вершинами'']] графа, а <math>E</math> ---
некоторой природы, называемых [[Вершина|''вершинами'']] графа, а <math>E</math>
подмножество двухэлементных подмножеств множества <math>V</math>, называемых
подмножество двухэлементных подмножеств множества <math>V</math>, называемых
[[Ребро|''ребрами'']] графа. Множества вершин и ребер графа <math>G</math> обозначают
[[Ребро|''ребрами'']] графа. Множества вершин и ребер графа <math>G</math> обозначают
Строка 9: Строка 9:
то говорят о <math>(n,m)</math>-графе <math>G</math>.  
то говорят о <math>(n,m)</math>-графе <math>G</math>.  


'''2.''' Пара <math>(V,E)</math>, где <math>V</math> ---
'''2.''' Пара <math>(V,E)</math>, где <math>V</math>
множество [[Вершина|''вершин'']] графа, а <math>E</math> --- множество [[Ребро|''ребер'']] ---
множество [[Вершина|''вершин'']] графа, а <math>E</math> множество [[Ребро|''ребер'']]
есть подмножество множества <math>V_{-}^{2} / \sim</math> классов
есть подмножество множества <math>V_{-}^{2} / \sim</math> классов
эквивалентности, на которые множество <math>V_{-}^{2} = \{(v,w) | v
эквивалентности, на которые множество <math>V_{-}^{2} = \{(v,w) | v
Строка 19: Строка 19:
[[Файл:Graph.png|800px]]
[[Файл:Graph.png|800px]]


'''3.''' Тройка <math>(V,E,P)</math>, где <math>V</math> --- множество [[Вершина|''вершин'']], <math>E</math>
'''3.''' Тройка <math>(V,E,P)</math>, где <math>V</math> множество [[Вершина|''вершин'']], <math>E</math>
--- множество объектов некоторой природы, отличной от природы
множество объектов некоторой природы, отличной от природы
вершин, называемых [[Ребро|''ребрами'']], <math>P</math> --- ''инцидентор'',
вершин, называемых [[Ребро|''ребрами'']], <math>P</math> ''инцидентор'',
сопоставляющий с каждым ребром <math>e \in E</math> пару ''граничных вершин''
сопоставляющий с каждым ребром <math>e \in E</math> пару ''граничных вершин''
<math>v</math> и <math>w</math> из <math>V</math>.  
<math>v</math> и <math>w</math> из <math>V</math>.  
Строка 30: Строка 30:
== См. также ==
== См. также ==


[[Абстрактный граф]],
* [[Абстрактный граф]],
[[Антисимметрический граф]],
* [[Альфа-Перестановочный граф|Альфа-перестановочный граф]],
[[Аранжируемый граф]],  
* [[Антисимметрический граф]],
[[Асимметрический граф]],
* [[Аранжируемый граф]],  
[[Бесконечный граф]],  
* [[Асимметричный граф]],
[[Бесконтурный граф]],
* [[Бесконечный граф]],  
[[Бихроматический граф]],
* [[Бесконтурный орграф]],
[[Вершинно-критический граф]],
* [[Бихроматический граф]],
[[Вершинно-непересекающиеся графы (подграфы)|Вершинно непересекающиеся графы]],
* [[Вершинно-критический граф]],
[[K-Вершинно-связный граф|K-вершинно-связный граф]],
* [[Вершинно-непересекающиеся графы (подграфы)|Вершинно непересекающиеся графы]],
[[Вершинно-симметрический граф]],
* [[K-Вершинно-связный граф|K-вершинно-связный граф]],
[[Взаимно связный граф]],  
* [[Вершинно-симметрический граф]],
[[Взвешенный граф]],
* [[Взаимно связный граф]],  
[[Внешнепланарный граф]],
* [[Взвешенный граф]],
[[Внешнеплоский граф]],
* [[Внешнепланарный граф]],
[[Вполне несвязный граф]],
* [[Внешнеплоский граф]],
[[Выпуклый прямолинейный граф]],
* [[Вполне несвязный граф]],
[[Гамильтонов граф]],
* [[Выпуклый прямолинейный граф]],
[[Гамильтоново-связный граф]],
* [[Гамильтонов граф]],
[[Геодезический граф]],
* [[Гамильтоново-связный граф]],
[[L-Геодезический граф|L-геодезический граф]],
* [[Геодезический граф]],
[[Строго геодезический граф]],
* [[L-Геодезический граф|L-геодезический граф]],
[[Геометрически двойственный граф]],
* [[Геометрически двойственный граф]],
[[Гипогамильтоновый граф]],
* [[Гипогамильтоновый граф]],
[[Дважды хордальный граф]],
* [[Гомеоморфные графы]],
[[Двойственно хордальный граф]],
* [[Графы Куратовского]],
[[Двойственный граф]],
* [[Дважды хордальный граф]],
[[Двудольный граф]],
* [[Двойственно хордальный граф]],
[[Двусторонний граф]],
* [[Двойственный граф]],
[[Дистанционно наследуемый граф]],
* [[Двудольный граф]],
[[Дистанционно-транзитивный граф]],
* [[Двусторонний граф]],
[[K-Дольный граф|K-дольный граф]],
* [[Дистанционно наследуемый граф]],
[[Звездно-экстремальный граф]],
* [[Дистанционно-транзитивный граф]],
[[Звездный граф]],
* [[K-Дольный граф|K-дольный граф]],
[[N-Звездный граф|N-звездный граф]],
* [[Звездно-экстремальный граф]],
[[Знаково-помеченный граф]],
* [[Звездный граф]],
[[Индифферентный граф]],
* [[N-Звездный граф|N-звездный граф]],
[[Индуктивный граф]],
* [[Знаковый помеченный граф]],
[[Информационный граф]],
* [[Изоморфные графы]],
[[Конечный граф]],
* [[Индифферентный граф]],
[[Г-Конечный граф|Гамма-конечный граф]],  
* [[Индуктивный граф]],
[[Корневой граф]],  
* [[Информационный граф]],
[[Критический граф]],  
* [[Конечный граф]],
[[Кубический граф]],  
* [[Г-Конечный граф|Гамма-конечный граф]],  
[[Локально-конечный граф]],  
* [[Корневой граф]],  
[[Локально-ограниченный граф]],  
* [[Коспектральные графы]],
[[Локально-счетный граф]],  
* [[Критический граф]],  
[[Максимальный сильно сингулярный граф]],  
* [[Кубический граф]],  
[[Максимальный сингулярный граф]],  
* [[Локально конечный граф]],  
[[Минимально связный граф]],  
* [[Локально ограниченный граф]],  
[[Многоугольный граф]],  
* [[Локально счетный граф]],  
[[Накрывающий граф]],  
* [[Максимальный сильно сингулярный граф]],  
[[K-Насыщенный граф|K-насыщенный граф]],  
* [[Максимальный сингулярный граф]],  
[[Неразделимый граф]],  
* [[Минимально связный граф]],  
[[Неразложимый граф]],  
* [[Многоугольный граф]],  
[[Несводимый граф]],  
* [[Накрывающий граф]],  
[[Несепарабельный граф]],  
* [[K-Насыщенный граф|K-насыщенный граф]],  
[[Нечетный граф]],  
* [[Неразделимый граф]],  
[[Обратный граф]], [[Общий граф]], [[Обыкновенный граф]], [[Однозначно раскрашиваемый граф]],  
* [[Неразложимый граф]],  
[[Однородный граф]], [[Односторонне связный граф]], [[Односторонний граф]],  
* [[Несводимый граф]],  
[[Одноциклический граф]], [[Ориентированно-циклически замкнутый граф]], [[Ориентированный граф]],  
* [[Несепарабельный граф]],  
[[Ориентируемый граф]], [[Панциклический граф]], [[J-Панциклический граф|J-панциклический граф]], [[Альфа-Перестановочный граф|Альфа-перестановочный граф]],  
* [[Нечетный граф]],  
[[Планарный граф]], [[Плоский граф]], [[(a,b)-Плоский граф|(a,b)-плоский граф]], [[Покрывающий граф]], [[Полный граф]],  
* [[Обратный орграф]],
[[Полный двудольный граф]], [[Полный k-дольный граф]], [[Полугамильтонов граф]], [[Полунесводимый граф]],  
* [[Общий граф]],
[[Полуэйлеров граф]], [[Помеченный граф]], [[Пороговый граф]], [[Почти однородный граф]], [[Правильный граф]],  
* [[Обыкновенный граф]],
[[Предельный граф]], [[Префиксный граф ширины n]], [[Прогрессивно конечный граф]], [[Прогрессивно ограниченный граф]],  
* [[Однозначно раскрашиваемый граф]],  
[[Производный граф]], [[Произвольно вычерчиваемый граф]], [[Произвольно гамильтонов граф]], [[Произвольно проходимый граф]],  
* [[Однородный граф]],
[[Простой граф]], [[Прямоугольный граф]], [[Псевдосимметрический граф]], [[Пустой граф]], [[Разборный граф]],  
* [[Односторонне связный орграф]],
[[Раскрашенный граф]], [[Реберно раскрашиваемый граф]], [[K-раскрашенный граф]], [[K-Раскрашиваемый граф|K-раскрашиваемый граф]],  
* [[Односторонний орграф]],  
[[Расщепляемый граф]], [[Реберно-критический граф]], [[Реберно  k-раскрашиваемый граф]], [[Расширенный нечетный граф]],  
* [[Одноциклический граф]],
[[Реберно-регулярный граф]], [[K-Реберно-связный граф|K-реберно-связный граф]], [[Реберно-симметрический граф]], [[Реберный граф]],  
* [[Ориентированно-циклически замкнутый граф]],
[[Регрессивно конечный граф]], [[Регрессивно ограниченный граф]], [[Регуляризуемый граф]],  
* [[Ориентированный граф]],  
[[Регулярный граф]], [[Регулярный степени 0 граф]], [[Реконструируемый граф]], [[Самодополнительный граф]],  
* [[Ориентируемый граф]],
[[Самонегативный граф]], [[Сбалансированный граф]], [[Сводимый граф]], [[Связный граф]], [[K-Связный граф|K-связный граф]],  
* [[Панциклический граф]],
[[2-Секционный граф|Два-секционный граф]], [[Сильно ориентированно-циклически замкнутый граф]],  
* [[J-Панциклический граф|J-панциклический граф]],
[[Сильно ориентированно-циклически-реберный граф]], [[Сильно связный граф]], [[Сильно-циклически замкнутый граф]],  
* [[Планарный граф]],
[[Сильно-циклически связный граф]], [[ симметрический граф]], [[Слабо связный граф]],  
* [[Плоский граф]],
[[Слабый орграф]], [[Смешанный граф]], [[Совершенный граф]], [[Соединяющий граф]], [[Соотнесенный неориентированный граф]],  
* [[(a,b)-Плоский граф|(a,b)-плоский граф]],
[[Составной граф]], [[Степенно-хордальный граф]], [[Строго хордальный граф]], [[Структурный граф]],  
* [[Покрывающий граф]],
[[Стягиваемый граф]], [[Счетный граф]], [[Топологический граф]], [[S-Топологический граф|S-топологический граф]], [[Тороидальный граф]],  
* [[Полный граф]],  
[[Тотальный граф]], [[Транзитивно ориентируемый граф]], [[Транзитивный граф]], [[K-Транзитивный граф|K-транзитивный граф]],  
* [[Полный двудольный граф]],
[[Триангулированный граф]], [[Тривиальный граф]], [[Узловой граф]], [[Унитарный граф]],  
* [[Полный k-дольный граф]],
[[K-Унитранзитивный граф|K-унитранзитивный граф]], [[Унициклический граф]], [[Упорядоченный граф]], [[Управляющий граф]],  
* [[Полугамильтонов граф]],
[[Хордальный граф]], [[Хордальный двудольный граф]], [[K-Хроматический граф|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.