Граф (неориентированный граф)

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]

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

См. также

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

Литература

{[Лекции]}