Содержание
12 отношения: Journal of Combinatorial Theory, Компонента связности графа, Построение Хайоша, Полный граф, Рёберно k-связный граф, Регулярный граф, Фактор-критический граф, Хайош, Дьёрдь, Эрдёш, Пал, Граф (математика), Граф-цикл, Ловас, Ласло.
- Раскраска графа
Journal of Combinatorial Theory
Journal of Combinatorial Theory, Series A и Series B — математические журналы, специализирующиеся на комбинаторике и связанных областях.
Посмотреть Критический граф и Journal of Combinatorial Theory
Компонента связности графа
Несвязный граф с тремя компонентами связности Компонента связности графа G (или просто компонента графа G) — максимальный (по включению) связный подграф графа G.
Посмотреть Критический граф и Компонента связности графа
Построение Хайоша
Построение Хайоша — это операция над графами, названная именем венгерского математика Дьёрдя Хайоша, которая может быть использована для построения любого критического графа или любого графа, хроматическое число которого не меньше некоторого заданного порога.
Посмотреть Критический граф и Построение Хайоша
Полный граф
По́лный граф — простой неориентированный граф, в котором каждая пара различных вершин смежна.
Посмотреть Критический граф и Полный граф
Рёберно k-связный граф
Рёберно k-связный граф — граф, который остаётся связным после удаления не более чем k-1 рёбер.
Посмотреть Критический граф и Рёберно k-связный граф
Регулярный граф
Регуля́рный (одноро́дный) граф — граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей.
Посмотреть Критический граф и Регулярный граф
Фактор-критический граф
наибольшими паросочетаниями подграфов, полученных удалением одной из вершин. Фактор-критический граф (или почти сочетаемый граф.) — это граф с вершинами, в котором каждый подграф с вершинами имеет совершенное паросочетание.
Посмотреть Критический граф и Фактор-критический граф
Хайош, Дьёрдь
Дьёрдь Ха́йош (Hajós György; 21 февраля 1912, Будапешт — 17 марта 1972, Будапешт) — венгерский математик и популяризатор.
Посмотреть Критический граф и Хайош, Дьёрдь
Эрдёш, Пал
Пал Э́рдёш (Erdős Pál; встречаются варианты написания Пауль Эрдёш, Paul Erdős, Paul Erdos; 26 марта 1913, Будапешт — 20 сентября 1996, Варшава) — один из самых знаменитых математиков XX века.
Посмотреть Критический граф и Эрдёш, Пал
Граф (математика)
Неориентированный граф с шестью вершинами и семью рёбрами Граф — абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.
Посмотреть Критический граф и Граф (математика)
Граф-цикл
В теории графов графом-циклом называется граф, состоящий из единственного цикла, или, другими словами, некоторого числа вершин, соединённых замкнутой цепью.
Посмотреть Критический граф и Граф-цикл
Ловас, Ласло
Ласло Ловас (Lovász László,; род. 9 марта 1948) — венгерский, известный работами по комбинаторике, за которые он был награждён многими престижными премиями.
Посмотреть Критический граф и Ловас, Ласло
См. также
Раскраска графа
- Ациклическая раскраска графа
- Вполне упорядочиваемый граф
- Гармоническая раскраска
- Гипотеза Албертсона
- Гипотеза Хадвигера (теория графов)
- Гипотеза Хивуда
- Гипотеза Эрдёша — Фабера — Ловаса
- Глубина дерева (теория графов)
- Дробная раскраска
- Жадная раскраска
- Задача Нелсона — Эрдёша — Хадвигера
- Звёздная раскраска
- Критический граф
- Однозначно раскрашиваемый граф
- Полная раскраска
- Построение Хайоша
- Раскраска графов
- Рёберная раскраска
- Слабая раскраска
- Снарк (теория графов)
- Теорема Брукса
- Теорема Визинга
- Теорема Галлаи — Хассе — Роя — Витавера
- Теорема де Брёйна — Эрдёша (теория графов)
- Теорема о раскраске дорог
- Тотальная раскраска
- Хроматический многочлен