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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 38: Строка 38:
[[Бихроматический граф]],
[[Бихроматический граф]],
[[Вершинно-критический граф]],
[[Вершинно-критический граф]],
[[Вершинно непересекающиеся графы]],
[[Вершинно-непересекающиеся графы (подграфы)|Вершинно непересекающиеся графы]],
[[K-вершинно-связный граф]],
[[K-Вершинно-связный граф|K-вершинно-связный граф]],
[[Вершинно-симметрический граф]],
[[Вершинно-симметрический граф]],
[[Взаимно связный граф]],  
[[Взаимно связный граф]],  
Строка 50: Строка 50:
[[Гамильтоново-связный граф]],
[[Гамильтоново-связный граф]],
[[Геодезический граф]],
[[Геодезический граф]],
[[L-геодезический граф]],
[[L-Геодезический граф|L-геодезический граф]],
[[Строго геодезический граф]],
[[Строго геодезический граф]],
[[Геометрически двойственный граф]],
[[Геометрически двойственный граф]],
Строка 61: Строка 61:
[[Дистанционно наследуемый граф]],
[[Дистанционно наследуемый граф]],
[[Дистанционно-транзитивный граф]],
[[Дистанционно-транзитивный граф]],
[[K-дольный граф]],
[[K-Дольный граф|K-дольный граф]],
[[Звездно-экстремальный граф]],
[[Звездно-экстремальный граф]],
[[Звездный граф]],
[[Звездный граф]],
[[N-звездный граф]],
[[N-Звездный граф|N-звездный граф]],
[[Знаково-помеченный граф]],
[[Знаково-помеченный граф]],
[[Индифферентный граф]],
[[Индифферентный граф]],
Строка 70: Строка 70:
[[Информационный граф]],
[[Информационный граф]],
[[Конечный граф]],
[[Конечный граф]],
[[Гамма-конечный граф]],  
[[Г-Конечный граф|Гамма-конечный граф]],  
[[Корневой граф]],  
[[Корневой граф]],  
[[Критический граф]],  
[[Критический граф]],  
Строка 82: Строка 82:
[[Многоугольный граф]],  
[[Многоугольный граф]],  
[[Накрывающий граф]],  
[[Накрывающий граф]],  
[[K-насыщенный граф]],  
[[K-Насыщенный граф|K-насыщенный граф]],  
[[Неразделимый граф]],  
[[Неразделимый граф]],  
[[Неразложимый граф]],  
[[Неразложимый граф]],  
Строка 91: Строка 91:
[[Однородный граф]], [[Односторонне связный граф]], [[Односторонний граф]],  
[[Однородный граф]], [[Односторонне связный граф]], [[Односторонний граф]],  
[[Одноциклический граф]], [[Ориентированно-циклически замкнутый граф]], [[Ориентированный граф]],  
[[Одноциклический граф]], [[Ориентированно-циклически замкнутый граф]], [[Ориентированный граф]],  
[[Ориентируемый граф]], [[Панциклический граф]], [[J-панциклический граф]], [[Альфа-перестановочный граф]],  
[[Ориентируемый граф]], [[Панциклический граф]], [[J-Панциклический граф|J-панциклический граф]], [[Альфа - Перестановочный граф|Альфа-перестановочный граф]],  
[[Планарный граф]], [[Плоский граф]], [[(a,b)-плоский граф]], [[Покрывающий граф]], [[Полный граф]],  
[[Планарный граф]], [[Плоский граф]], [[(a,b)-Плоский граф|(a,b)-плоский граф]], [[Покрывающий граф]], [[Полный граф]],  
[[Полный двудольный граф]], [[Полный k-дольный граф]], [[Полугамильтонов граф]], [[Полунесводимый граф]],  
[[Полный двудольный граф]], [[Полный k-дольный граф]], [[Полугамильтонов граф]], [[Полунесводимый граф]],  
[[Полуэйлеров граф]], [[Помеченный граф]], [[Пороговый граф]], [[Почти однородный граф]], [[Правильный граф]],  
[[Полуэйлеров граф]], [[Помеченный граф]], [[Пороговый граф]], [[Почти однородный граф]], [[Правильный граф]],  
Строка 98: Строка 98:
[[Производный граф]], [[Произвольно вычерчиваемый граф]], [[Произвольно гамильтонов граф]], [[Произвольно проходимый граф]],  
[[Производный граф]], [[Произвольно вычерчиваемый граф]], [[Произвольно гамильтонов граф]], [[Произвольно проходимый граф]],  
[[Простой граф]], [[Прямоугольный граф]], [[Псевдосимметрический граф]], [[Пустой граф]], [[Разборный граф]],  
[[Простой граф]], [[Прямоугольный граф]], [[Псевдосимметрический граф]], [[Пустой граф]], [[Разборный граф]],  
[[Раскрашенный граф]], [[Реберно раскрашиваемый граф]], [[K-раскрашенный граф]], [[K-раскрашиваемый граф]],  
[[Раскрашенный граф]], [[Реберно раскрашиваемый граф]], [[K-раскрашенный граф]], [[K-Раскрашиваемый граф|K-раскрашиваемый граф]],  
[[Расщепляемый граф]], [[Реберно-критический граф]], [[Реберно  k -раскрашиваемый граф]], [[Расширенный нечетный граф]],  
[[Расщепляемый граф]], [[Реберно-критический граф]], [[Реберно  k-раскрашиваемый граф]], [[Расширенный нечетный граф]],  
[[Реберно-регулярный граф]], [[K-реберно-связный граф]], [[Реберно-симметрический граф]], [[Реберный граф]],  
[[Реберно-регулярный граф]], [[K-Реберно-связный граф|K-реберно-связный граф]], [[Реберно-симметрический граф]], [[Реберный граф]],  
[[Регрессивно конечный граф]], [[Регрессивно ограниченный граф]], [[Регуляризуемый граф]],  
[[Регрессивно конечный граф]], [[Регрессивно ограниченный граф]], [[Регуляризуемый граф]],  
[[Регулярный граф]], [[Регулярный степени 0 граф]], [[Реконструируемый граф]], [[Самодополнительный граф]],  
[[Регулярный граф]], [[Регулярный степени 0 граф]], [[Реконструируемый граф]], [[Самодополнительный граф]],  
[[Самонегативный граф]], [[Сбалансированный граф]], [[Сводимый граф]], [[Связный граф]], [[K-связный граф]],  
[[Самонегативный граф]], [[Сбалансированный граф]], [[Сводимый граф]], [[Связный граф]], [[K-Связный граф|K-связный граф]],  
[[Два-секционный граф]], [[Сильно ориентированно-циклически замкнутый граф]],  
[[2-Секционный граф|Два-секционный граф]], [[Сильно ориентированно-циклически замкнутый граф]],  
[[Сильно ориентированно-циклически-реберный граф]], [[Сильно связный граф]], [[Сильно-циклически замкнутый граф]],  
[[Сильно ориентированно-циклически-реберный граф]], [[Сильно связный граф]], [[Сильно-циклически замкнутый граф]],  
[[Сильно-циклически связный граф]], [[ симметрический граф]], [[Слабо связный граф]],  
[[Сильно-циклически связный граф]], [[ симметрический граф]], [[Слабо связный граф]],  
[[Слабый орграф]], [[Смешанный граф]], [[Совершенный граф]], [[Соединяющий граф]], [[Соотнесенный неориентированный граф]],  
[[Слабый орграф]], [[Смешанный граф]], [[Совершенный граф]], [[Соединяющий граф]], [[Соотнесенный неориентированный граф]],  
[[Составной граф]], [[Степенно-хордальный граф]], [[Строго хордальный граф]], [[Структурный граф]],  
[[Составной граф]], [[Степенно-хордальный граф]], [[Строго хордальный граф]], [[Структурный граф]],  
[[Стягиваемый граф]], [[Счетный граф]], [[Топологический граф]], [[S-топологический граф]], [[Тороидальный граф]],  
[[Стягиваемый граф]], [[Счетный граф]], [[Топологический граф]], [[S-Топологический граф|S-топологический граф]], [[Тороидальный граф]],  
[[Тотальный граф]], [[Транзитивно ориентируемый граф]], [[Транзитивный граф]], [[K-транзитивный граф]],  
[[Тотальный граф]], [[Транзитивно ориентируемый граф]], [[Транзитивный граф]], [[K-Транзитивный граф|K-транзитивный граф]],  
[[Триангулированный граф]], [[Тривиальный граф]], [[Узловой граф]], [[Унитарный граф]],  
[[Триангулированный граф]], [[Тривиальный граф]], [[Узловой граф]], [[Унитарный граф]],  
[[K-унитранзитивный граф]], [[Унициклический граф]], [[Упорядоченный граф]], [[Управляющий граф]],  
[[K-Унитранзитивный граф|K-унитранзитивный граф]], [[Унициклический граф]], [[Упорядоченный граф]], [[Управляющий граф]],  
[[Хордальный граф]], [[Хордальный двудольный граф]], [[K-хроматический граф]], [[Цветной граф Кэлли]],  
[[Хордальный граф]], [[Хордальный двудольный граф]], [[K-Хроматический граф|K-хроматический граф]], [[Цветной граф Кэлли]],  
[[Циклически жесткий граф]], [[Циклически замкнутый граф]], [[Циклический граф]],  
[[Циклически жесткий граф]], [[Циклически замкнутый граф]], [[Циклический граф]],  
[[Циркулянтный граф]], [[Частичный граф]], [[Четный граф]], [[Эйлеров граф]], [[Гомеоморфные графы]],  
[[Циркулянтный граф]], [[Частичный граф]], [[Четный граф]], [[Эйлеров граф]], [[Гомеоморфные графы]],  

Версия от 13:12, 9 июня 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. Общее название как для неориентированного, так и для ориентированного графов.

См. также

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

Литература

[Лекции]