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

Материал из WikiGrapp
Перейти к:навигация, поиск
(Литература)
 
Строка 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. Пара (V,E), где V — непустое множество объектов некоторой природы, называемых вершинами графа, а E — подмножество двухэлементных подмножеств множества V, называемых ребрами графа. Множества вершин и ребер графа G обозначают V(G) и E(G) соответственно. Если |V(G)| = n и |E(G)| = m, то говорят о (n,m)-графе G.

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

Graph.png

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

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

См. также

Литература

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