рисунок показывает граф (слева, с синими вершинами) и его рёберный граф (справа, с зелёными вершинами). Каждая вершина рёберного графа помечена парой номеров...

словами, рёберный граф гиперграфа — это граф пересечений семейства конечных множеств. Понятие является обобщением рёберного графа обычного графа. Вопросы...

Примеры разрезов в графе 5-рёберный разрез в 6-рёберном графе (не бонд) 2-рёберный разрез в том же графе (бонд) Поток на графе — это набор целых чисел...

что рёберный граф двудольного графа совершенен. Поскольку рёберные графы двудольных графов совершенны, дополнения рёберных графов двудольных графов тоже...

бесконечности. Рёберное покрытие — множество рёбер графа такое, что каждая вершина инцидентна хотя бы одному ребру из этого множества. Рёберный граф неориентированного...

Рёберно совершенный граф — это граф, рёберный граф которого является совершенным. Эквивалентно, это графы, у которых каждый простой цикл нечётной длины...

раскраски графов, все остальные задачи в этой области могут быть сведены к ней. Например, раскраска рёбер графа — это раскраска вершин его рёберного графа, а...

Граф призмы — рёберный граф одной из призм. Индивидуальные графы можно назвать согласно ассоциированным телам: Граф треугольной призмы — 6 вершин, 9 рёбер...

клики, содержащие v {\displaystyle v} , идут последовательно. Рёберный граф — это граф рёбра которого могут быть покрыты кликами без общих рёбер, притом...

стягивание графа, и т.д. Сложные операции создают новый граф из начального при помощи комплексных изменений, таких как: Рёберный граф Двойственный граф Дополнение...

рёберный граф L(K8) полного графа K8. Графы Чана названы именем Ли-Чиена Чана, который доказал, что, за исключением этих трёх графов, любой рёберный граф...

изоморфизме графов , сформулированная Хасслером Уитни в 1932 году, гласит, что два связных графа изоморфны, тогда и только тогда, когда их рёберные графы изоморфны...

для вложения графов в многообразия. Понятие двойственности графов отличается от рёберно-вершинной двойственности (рёберный граф) графа и эти два понятия...

В теории графов рёберно-транзитивным (англ.  edge-transitive) называется такой граф G , для двух любых рёбер которого e1 и e2 существует автоморфизм, отображающий...

Рёберная раскраска — назначение «цветов» рёбрам графа таким образом, что никакие два смежных ребра не имеют один и тот же цвет. Рёберная раскраска — это...

как рёберный граф куба, а граф Пэли с девятью вершинами является рёберным графом коммунального графа K 3 , 3 {\displaystyle K_{3,3}} . Рёберный граф графа...

Производящая функция числа k-рёберных паросочетаний в графе называется многочлен паросочетаний. Пусть G — граф и mk — число k-рёберных паросочетаний. Полиномом...

5-регулярным графом, другой имеет 80 рёбер и является 10-регулярным графом. 80-рёберный вариант — это половинный граф куба[англ.] 5-го порядка. Назван графом Клебша...

Путь в графе — последовательность вершин, в которой каждая вершина соединена со следующей ребром. Пусть G — неориентированный граф. Путём в G называется...

в теории графов. Назван в честь Юлиуса Петерсена, построившего его в 1898 году как наименьший кубический граф без мостов, не имеющий рёберной раскраски...

произведение графов регулярных блужданий является графом регулярных блужданий. В общем случае рёберный граф регулярных блужданий не является графом регулярных...

же пределах граф содержит цикл длины k {\displaystyle k} , содержащий вершину v {\displaystyle v} . Похожим образом граф является рёберно панциклическим...

включает леса, графы без циклов. Рёберные графы двудольных графов (смотри теорему Кёнига). Ладейные графы (рёберные графы полных двудольных графов) являются...

1-разложение k-регулярного графа — это рёберная раскраска k цветами. 2-фактор — это набор циклов, которые покрывают все вершины графа. Если граф 1-факторизуем (то...

числу вершин гиперграфа, рёберный граф которого совпадает с G. Кляйн и Марграф определяют аналогично линейное число пересечений графа как минимальное число...

множества в графах без клешней; описание совершенных графов без клешней. Графам без клешней посвящены сотни статей и несколько обзоров. Рёберный граф L(G) любого...

0 до p − 1 вершинам. Говорят, что граф G рёберно грациозный, если позволяет рёберную грациозную разметку. Рёберную грациозную разметку первым ввёл С....

Рёберно k-связный граф — граф, который остаётся связным после удаления не более чем k − 1 {\displaystyle k-1} рёбер. Часто вместо рёберно k-связный граф...

удаления (получение минимального остовного дерева из связного рёберно взвешенного графа). На задачу о нахождении минимального остовного дерева похожа...

совпадает с рёберным графом графа G {\displaystyle G} . Граф B ( B ( G ) ) {\displaystyle B(B(G))} имеет вершину для каждой точки сочленения графа G {\displaystyle...

двудольный граф является подграфом полного двудольного графа, а значит любой рёберный граф двудольного графа является порождённым подграфом ладейного графа. Рёберные...