4183
правки
(Создана новая страница размером Это --- пример.) |
KEV (обсуждение | вклад) Нет описания правки |
||
(не показано 15 промежуточных версий 3 участников) | |||
Строка 1: | Строка 1: | ||
'''Граф (неориентированный граф)''' (''[[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. | |||
[[Категория:Неориентированные графы]] |