Просмотр кода страницы Граф (неориентированный граф)

'''Граф (неориентированный граф)''' (''[[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.


[[Категория:Неориентированные графы]]