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