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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показано 11 промежуточных версий 3 участников)
Строка 1: Строка 1:
''' 1.''' Пара <math>(V,E)</math>, где <math>V</math> --- непустое множество заданных объектов
'''Граф (неориентированный граф)''' (''[[Graph (undirected graph)]]'') — это
некоторой природы, называемых ''вершинами'' графа, а <math>E</math> ---
 
 
''' 1.''' Пара <math>(V,E)</math>, где <math>V</math> непустое множество объектов
некоторой природы, называемых [[Вершина|''вершинами'']] графа, а <math>E</math>
подмножество двухэлементных подмножеств множества <math>V</math>, называемых
подмножество двухэлементных подмножеств множества <math>V</math>, называемых
''ребрами'' графа. Множества вершин и ребер графа <math>G</math> обозначают
[[Ребро|''ребрами'']] графа. Множества вершин и ребер графа <math>G</math> обозначают
<math>V(G)</math> и <math>E(G)</math> соответственно. Если <math>|V(G)| = n</math> и <math>|E(G)| = m</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>.  
то говорят о <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
Строка 14: Строка 17:
(v_{2},w_{2})</math> или <math>(v_{1},w_{1}) = (w_{2},v_{2}).</math>
(v_{2},w_{2})</math> или <math>(v_{1},w_{1}) = (w_{2},v_{2}).</math>


'''3.''' Тройка <math>(V,E,P)</math>, где <math>V</math> --- множество ''вершин'', <math>E</math>
[[Файл:Graph.png|800px]]
--- множество объектов некоторой природы, отличной от природы
 
вершин, называемых ''ребрами'', <math>P</math> --- ''инцидентор'',
'''3.''' Тройка <math>(V,E,P)</math>, где <math>V</math> множество [[Вершина|''вершин'']], <math>E</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>.  


'''4.''' Общее название как для
'''4.''' Общее название как для
неориентированного, так  и  для  ориентированного графов.
[[Неориентированный граф|неориентированного]], так  и  для  [[Ориентированный граф|ориентированного графов]].


== См. также ==
== См. также ==


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