Темы

Теория графов

Graph Theory · 58 статей

  1. Деревья и леса в теории графов

    Деревья в теории графов: определения, свойства (связность, ацикличность). Леса, ориентированные деревья и полилеса. Основы для структур данных.

    #11404 · 5 мин чтения

  2. Запрещенные подграфы планарных графов и теорема Куратовского.

    Теорема Куратовского о планарных графах: характеристика планарности через запрещенные подграфы (K5 и K3,3). Определение и свойства планарных графов.

    #12768 · 3 мин чтения

  3. Гамильтонов путь и цикл: поиск и алгоритмы решения

    Поиск гамильтонова пути/цикла в графе: определение, сложность, алгоритмы. Теория графов и информатики. Существование пути, посещающего все вершины.

    #47127 · 5 мин чтения

  4. Разложение графа на дерево и ширина дерева

    Дерево разложения графа: определение, применение в теории графов и алгоритмах. Ускорение вычислений, оптимизация запросов, вероятностный вывод.

    #49543 · 3 мин чтения

  5. Циклы и ациклические графы: определения и свойства

    Циклы в графах: определение, типы (направленные, ненаправленные). Ациклические графы и их свойства. Теория графов простым языком.

    #51636 · 5 мин чтения

  6. Двудольные графы: теория и свойства

    Двудольный граф: определение, свойства и примеры. Разделение вершин на независимые множества, отсутствие циклов нечетной длины, раскраска графа.

    #66233 · 10 мин чтения

  7. Компоненты связности графа: теория и применение

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

    #66530 · 5 мин чтения

  8. Биекция между множествами вершин графов и изоморфизм графов

    Изоморфизм графов: биекция между вершинами, сохраняющая связи. Автоморфизмы, классы изоморфизма и сложная проблема проверки изоморфности в теории графов.

    #66743 · 6 мин чтения

  9. Задача о поиске полных подграфов

    Поиск полных подграфов (клик) в теории графов: определение, задачи (максимальный клик, вес), применение в соцсетях. Сложность вычислений.

    #67031 · 22 мин чтения

  10. Внешнепланарные графы: свойства и характеристики

    Внешнепланарные графы: свойства, характеристики (K4, K2,3), гамильтоновы циклы, 3-раскрашимость, ширина дерева ≤2. Теория графов.

    #84000 · 6 мин чтения

  11. Миноры графов и их свойства

    Миноры графов: определение, теорема Вагнера о планарности, теорема Робертсона-Сеймура. Монотонность миноров и частичный порядок графов. Теория графов.

    #84126 · 10 мин чтения

  12. Графы пересечений интервалов на прямой

    Интервальные графы: определение, свойства и алгоритмы. Графы пересечений интервалов на числовой прямой – линейное время распознавания и оптимальная раскраска.

    #85795 · 5 мин чтения

  13. Клик в теории графов: определение и свойства

    Клик в теории графов: определение, свойства и алгоритмы поиска. NP-полная задача о клике и её применение в математике и компьютерных науках.

    #111939 · 4 мин чтения

  14. Независимые множества в графах

    Независимое множество в теории графов: определение, свойства и связь с кликами в дополнительном графе. Ключевые понятия и терминология.

    #111945 · 7 мин чтения

  15. Пути и обходы в графах

    Путь в графе: определение, виды (направленные, ненаправленные), свойства. Основы теории графов и алгоритмы поиска путей между вершинами.

    #128060 · 4 мин чтения

  16. Вершина графа: основные понятия и типы

    Вершина графа: основное понятие в теории графов. Узлы и рёбра, свойства, смежность и применение в дискретной математике и сетях.

    #128061 · 3 мин чтения

  17. Совершенные графы: связь раскраски и клик

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

    #132211 · 22 мин чтения

  18. Совершенные графы и их дополнения: теорема о совершенстве графов.

    Перфектные графы в теории графов: теорема о совершенстве и ее связь с комплементарными графами. Неперфектность циклов и антициклов.

    #132222 · 4 мин чтения

  19. Соответствия между графами, сохраняющие структуру

    Гомоморфизмы графов: отображение структуры графов, обобщение раскрасок и решение задач ограничений. Алгебраические структуры и сложность вычислений.

    #132891 · 5 мин чтения

  20. Разложение графа на сильно связные компоненты

    Сильная связность графов: определение, проверка и поиск сильно связных компонент за линейное время (O(V+E)). Математическая теория ориентированных графов.

    #133841 · 5 мин чтения

  21. Раскраска рёбер графа: теория и алгоритмы.

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

    #134226 · 27 мин чтения

  22. Сильная раскраска графов и сильное хроматическое число

    Раскраска вершин графов: определение сильной раскраски, сильный хроматический номер sχ(G) и его свойства. Теория графов и оптимизация раскраски.

    #134250 · 2 мин чтения

  23. Дробное раскрашивание графов и задачи планирования

    Фрактальное раскрашивание графов: обобщение обычной раскраски. Каждой вершине назначается набор цветов, смежные вершины не имеют общих цветов. Теория графов.

    #134430 · 2 мин чтения

  24. Хордальные графы: свойства и алгоритмы

    Хордальные графы: определение, свойства и характеристики. Графы, где каждый цикл ≥4 имеет хорду. Порядок совершенной элиминации, совершенные графы.

    #140573 · 7 мин чтения

  25. Кографы: свойства, характеризации и структура

    Кографы: теория графов, комплементарные и разрывные объединения. Структура, алгоритмы, максимальные клики, применение в различных графах.

    #190036 · 8 мин чтения

  26. Корневые графы: определения и применения

    Корневой граф в теории графов: определение, свойства и применение. Изучение ориентированных и неориентированных графов с выделенной корневой вершиной.

    #210959 · 3 мин чтения

  27. Графы пересечений хорд и раскраска графов

    Графы пересечений хорд: определение, свойства и раскраска. NP-полная задача определения хроматического числа графов окружностей и проверка раскраски в 4 цвета.

    #213395 · 3 мин чтения

  28. Минимальные разделители вершин в графах

    Разделители вершин в теории графов: определение, применение к сетчатым графам. Минимизация размера разделяющего множества для эффективного разделения графа.

    #223344 · 3 мин чтения

  29. Нулевой граф и пустой граф в теории графов

    Нулевой граф в теории графов: определение, свойства и отличия от пустого графа. Уникальный граф без вершин и рёбер, регулярный граф 0-й степени.

    #225263 · 2 мин чтения

  30. Теория графов: связность и отсекающие множества

    Теория графов: основные понятия связности, сильной связности и связных компонент. Математика и информатика – определения и примеры.

    #234446 · 6 мин чтения

  31. Свойства графов, зависящие от абстрактной структуры

    Свойства графов, зависящие от абстрактной структуры. Инварианты графов – характеристики, сохраняющиеся при изоморфизмах. Теория графов, определения и примеры.

    #238693 · 1 мин чтения

  32. Индуцированный подграф: определение и свойства

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

    #238696 · 2 мин чтения

  33. Число Хадвигера графа и его свойства

    Ха́двигеровский номер графа: определение, свойства и связь с хроматическим числом. NP-трудность вычисления и характеризация графов с малым номером.

    #239723 · 4 мин чтения

  34. Метрическое измерение графов: сложность, границы и специальные случаи.

    Метрическое измерение графа: определение, сложность (NP-полная задача). Разрешающие множества, базисы и связь с метрическими пространствами. Теория графов.

    #243929 · 5 мин чтения

  35. Полидеревья и ориентированные графы: теория и применения.

    Полидерево в теории графов: определение, свойства и связь с ориентированными графами. Узнайте о полилесах и ациклических графах!

    #246235 · 2 мин чтения

  36. Доминирующие множества в графах: определение и свойства

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

    #247536 · 7 мин чтения

  37. Доматическое разбиение графа: свойства и сложность поиска

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

    #249861 · 3 мин чтения

  38. Максимальные независимые множества в графах: комбинаторные аспекты и алгоритмы

    Максимальное независимое множество в теории графов: определение, свойства и примеры. Независимое множество, не являющееся подмножеством другого.

    #252001 · 7 мин чтения

  39. Минимальный вершинный набор обратной связи: сложность, алгоритмы и свойства

    Определение и применение множества вершин обратной связи (FVS) в теории графов. NP-полная задача с использованием в ОС, БД и проектировании чипов.

    #258732 · 2 мин чтения

  40. Задача о монохроматическом треугольнике

    Монохроматический треугольник: NP-полная задача теории графов о разделении рёбер на два треугольник-свободных подграфа. Оптимизация и алгоритмы.

    #259065 · 2 мин чтения

  41. Арборитность графа: определение, свойства и алгоритмы вычисления.

    Арборесценция графа: минимальное число лесов для покрытия рёбер. Теорема Нэша-Уильямса, пример K4,4. Оптимизация и анализ графов в теории.

    #314219 · 4 мин чтения

  42. Разложение Дюлмажа — Мендельсона двудольного графа

    Разложение Дульмажа-Мендельсона: разбиение вершин двудольного графа для поиска совершенного паросочетания. Теория графов, алгоритм Блоссома.

    #330017 · 2 мин чтения

  43. Плотные и разреженные графы: определение и свойства

    Плотный граф в математике: определение, плотность и отличие от разреженных графов. Рассмотрение количества ребер и максимального числа соединений.

    #337350 · 3 мин чтения

  44. Размерность частично упорядоченных множеств

    Размерность частично упорядоченного множества в математике: минимальное число полных порядков, дающих частичный порядок. Определение и примеры.

    #363166 · 3 мин чтения

  45. Порядковое измерение инцидентных множеств планарных графов

    Теория графов: теорема Шнайдера об измерении порядка инцидентных позиций планарных графов. Определение, свойства и применение в математике.

    #363179 · 2 мин чтения

  46. Инвариант Колена де Вердьера: свойства и связи с графами

    Инвариант графа де Вердьера: определение, связь со спектром операторов Шрёдингера, внешнепланарными графами и раскраской графов. Математика.

    #363400 · 2 мин чтения

  47. Запрещенные миноры планарных графов

    Планарные графы: теорема Вагнера о запрещенных минорах K5 и K3,3. Характеризация планарности, вложения графов, стяжение ребер и миноры. Теория графов.

    #363489 · 4 мин чтения

  48. Графы пересечения единичных дисков на плоскости

    Графы единичных дисков: определение, свойства и примеры. Изучение пересечений дисков в геометрии, случайные структуры и ограничения построения графов.

    #400566 · 3 мин чтения

  49. Транзитивное сокращение ориентированного графа

    Транзитивное сокращение графа: удаление избыточных рёбер с сохранением связности. Определение, свойства, сложность вычисления и уникальность.

    #404728 · 5 мин чтения

  50. Сжатие ребра и идентификация вершин в графе.

    Сжатие ребра в теории графов: удаление ребра и объединение вершин. Основная операция для миноров графов, менее строгая чем идентификация вершин.

    #404770 · 4 мин чтения

  51. Алгебраическое кодирование связности графа: Полином Татта

    Полином Тута: ключевой инструмент теории графов для анализа связности. Обобщение задач раскраски, связь с физикой и информатикой.

    #412549 · 5 мин чтения

  52. Ширина дерева графа: определение и свойства

    Ширина дерева в теории графов: определение, связь с деревьями и лесами, графы с шириной ≤2 (серийно-параллельные). k-деревья и частичные k-деревья.

    #417650 · 8 мин чтения

  53. Размещение графов на полуплоскостях и книжное вложение графов

    Размещение графов на полуплоскостях: определение book embedding, толщина книги (pagenumber, stacknumber) и связанные инварианты графов. Теория графов.

    #417687 · 15 мин чтения

  54. k-связность графа: определение и свойства

    Связность графа: определение k-связности, удаление рёбер и сохранение связности. Изучение краевой связности графов с 1869 года. Теория графов.

    #451403 · 2 мин чтения

  55. Moral graph

    #464034 · 1 мин чтения

  56. Dependency graph

    #472002 · 2 мин чтения

  57. Haven (graph theory)

    #477051 · 3 мин чтения

  58. Grundy number

    #481493 · 3 мин чтения