Темы

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

Graph Theory · 57 статей

  1. Разреженные графы с высокой связностью

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

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

  2. Длина кратчайшего цикла в графе.

    Длина кратчайшего цикла в графе (окружность графа) – важное понятие в теории графов. Узнайте, как определить окружность и что значит отсутствие циклов.

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

  3. Плоские графы и их свойства

    Планарные графы: определение, свойства и примеры (K5, K4, K3,3). Встраивание графов в плоскость без пересечения ребер. Теория графов простым языком.

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

  4. Совершенное соответствие в графе

    Совершенное соответствие в теории графов: определение, свойства и примеры. Покрытие всех вершин графа подмножеством рёбер. Максимальное соответствие.

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

  5. О опровержении гипотезы Тейта о гамильтоновом цикле в планарных кубических графах

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

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

  6. Задача о трёх коммуникациях: история и невозможность решения

    Математическая головоломка о соединении домов и коммуникаций без пересечений. Классическая задача, не имеющая решения на плоскости, но решаемая на других поверхностях.

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

  7. Полный граф: свойства и характеристики

    Полный граф в теории графов: определение, свойства и история. От Эйлера до Рамона Лулля. Узнайте о полных графах и "мистической розе".

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

  8. Регулярные графы: определение, свойства и классификация

    Регулярные графы в теории графов: определение, свойства и классификация. Вершины одинаковой степени, направленные графы, кубические графы.

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

  9. Семь мостов Кёнигсберга: Основы теории графов

    Семь мостов Кёнигсберга: классическая задача теории графов, решённая Эйлером в 1736 году. Основа топологии и математического анализа маршрутов.

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

  10. Граф Петерсена: свойства и характеристики

    Граф Петерсена: кубический граф с 10 вершинами и 15 ребрами. Важный пример и контрпример в теории графов, названный в честь Юлиуса Петерсена.

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

  11. Обобщение теории графов: Гиперграфы

    Гиперграф: обобщение теории графов в математике. Ребра соединяют любое число вершин, в отличие от обычных графов. Определение, порядок и размер гиперграфа.

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

  12. Гамильтонов путь и цикл в теории графов

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

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

  13. Подпространства чётной степени графа

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

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

  14. Теория графов: основные понятия и определения.

    Графы в теории графов: вершины и рёбра, связи между объектами. Определение, виды (направленные/ненаправленные) и визуальное представление графов.

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

  15. Эйлеров путь и цикл в графах

    Эйлеров путь и цикл в теории графов: определение, условия существования (четная степень вершин), связь с задачей о кенигсбергских мостах Эйлера.

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

  16. Полный двудольный граф: свойства и применение.

    Полный двудольный граф: определение, история (с 1669г!), свойства и связь с работами Эйлера и Рамона Лулля. Теория графов и её развитие.

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

  17. Спектральная теория графов: линейно-алгебраический подход

    Спектральная теория графов: линейная алгебра и свойства графов через матрицы смежности и Лапласа. Изучение собственных значений и инвариантов графа.

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

  18. Автоморфные графы: теория и примеры

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

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

  19. Графы, обладающие краевой автоматией

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

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

  20. Линейный граф: математическое понятие и свойства

    Линейный граф в теории графов: определение, построение и свойства. Представление смежностей рёбер графа G. Восстановление графа по его линейному графу.

    #132792 · 12 мин чтения

  21. Уникально раскрашиваемые графы

    Уникально раскрашиваемые графы в теории графов: определение, свойства и примеры (полные графы, k-деревья, аполлоновы сети). Оптимальная раскраска.

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

  22. Снарки: графы без 3-раскраски рёбер

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

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

  23. Вложение графа в трехмерное пространство без сцепленных циклов.

    Встраивание графов в 3D без циклов: определение, свойства и типы (linkless, flat, intrinsically linked). Теория графов и топология.

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

  24. Рамануджановы графы: теория, свойства и построения.

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

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

  25. Кубические графы: теория, свойства и примеры.

    Кубические графы: определение, свойства и классификация в теории графов. Вершины степени 3, 3-регулярные графы, бикубические графы и перепись Фостера.

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

  26. Граф Хигмана — Симса: свойства и построение

    Граф Хигмана-Симса: сильно регулярный граф (100 вершин, 22 ребра). Свойства, конструкция, связь с группами Хигмана-Симса и графом Хоффмана-Синглтона.

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

  27. Дополнительный граф и его свойства

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

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

  28. Степень вершины графа: определение и свойства

    Степень вершины графа: определение, обозначения (max, min), валентность. Теория графов, мультиграфы, регулярные графы. Основы и примеры.

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

  29. Граф Хивуда: свойства и характеристики

    Граф Хьювуда: кубический граф с 14 вершинами и 21 ребром. Является 6-клеткой, дистанционно-транзитивным и дистанционно-регулярным графом.

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

  30. Граф Татта — Коксетера: свойства и структура

    Граф Татта-Коксетера: кубический граф с 30 вершинами, минимальный обхват 8. Свойства, конструкция (граф Леви обобщенного четырехугольника W2) и история открытия.

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

  31. Графы Леви: теория и примеры конфигураций.

    Графы Леви: определение, свойства и связь с инцидентными структурами в комбинаторной математике. Минимальная длина цикла – 6. Оптимизация SEO.

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

  32. Сильно регулярные графы

    Сильно регулярные графы в теории графов: определение, параметры (v, k, λ, μ), связь с комплементарными графами и другими типами графов.

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

  33. Хроматический полином: обзор и свойства

    Хроматический полином в теории графов: определение, применение для решения задачи о четырёх цветах, связь с моделью Поттса и обобщение Tutte.

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

  34. Симметричные и полутранзитивные графы: обзор и примеры

    Симметричные графы в теории графов: определение, свойства, автоморфизмы и транзитивность. Изучаем полутранзитивные графы и граф Холта.

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

  35. Разметка графов: типы и свойства

    Разметка графов в теории графов: назначение меток вершинам и ребрам. Виды графов с метками, определение и свойства. Математические основы и примеры.

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

  36. Алгебраическая теория графов

    Алгебраическая теория графов: применение алгебраических методов к задачам о графах. Линейная алгебра, теория групп, инварианты графов – ключевые области.

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

  37. Топологическая теория графов

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

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

  38. Тороидальные графы: свойства и характеристики

    Тороидальный граф: определение, свойства и примеры (Heawood, K7, Петерсен). Графы, встраиваемые в тор, и их связь с планарными графами. Теория графов.

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

  39. Положительно определенные интегральные множества повторных точек ранга 24 и решетки Нимейера

    Нимейер решетки: математическая классификация 24 положительно определенных четных унимодулярных решеток ранга 24. Лич решетка и свойства.

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

  40. Краевая изящность графов: определение и свойства

    Графическая теория: определение и свойства грациозной маркировки рёбер графа. Математическое описание, обозначения рёбер и вершин, формулы маркировки.

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

  41. Теорема о пяти красках для планарных карт

    Теорема о пяти красках: докажите, что для раскраски любой плоской карты достаточно 5 цветов. Основана на работе Кемпа и Хьювуда, проще теоремы о четырёх красках.

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

  42. Двойственный граф: теория и применения

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

    #319030 · 18 мин чтения

  43. Полусимметричные графы: краевая транзитивность и регулярность без вершинной транзитивности

    Полусимметричные графы: определение, свойства и примеры (граф Фолькмана). Регулярные и реберно-транзитивные, но не вершинно-транзитивные графы в теории графов.

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

  44. Графы в виде книг: свойства и применения

    Графы-книги в теории графов: определение, виды (четырёхугольные), свойства (расщепляемые графы). Пример графа без гармоничной маркировки.

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

  45. Двунаправленные графы

    Бидиректный граф: определение, типы рёбер (экстравертные, интровертные, направленные). Обобщение понятия ориентированного графа в теории графов.

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

  46. Двуграфы: свойства, связь с графами и переключениями.

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

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

  47. Тензорное произведение графов

    Тензорное произведение графов: определение, свойства и связь с матрицами смежности. Альфред Уайтхед и Бертранд Рассел, Principia Mathematica. Теория графов.

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

  48. Системы вращений: комбинаторные вложения и отображения на поверхностях.

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

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

  49. Факторизация графов и связанные проблемы

    Факторы графов в теории графов: определения, k-факторы, k"-факторизация. Совершенные паросочетания, раскраска рёбер и циклы в графах.

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

  50. Геометрическая теория графов

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

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

  51. Циркулянтные графы и циклические группы симметрий

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

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

  52. Графы Мура: Определение и свойства

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

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

  53. Магические графы и метки: обзор и определения

    Магические графы: определение, типы (супермагические, вершинно-магические, тотально-магические) и варианты маркировок. Теория графов и её применения.

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

  54. Гипотеза Ловаша о гамильтоновых путях в графах

    Гипотеза Ловаса в теории графов: о существовании гамильтонова пути в связных вершинно-транзитивных графах. Открытая проблема с 1969 года, контрпримеры Бабая.

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

  55. Четвертичные графы: свойства и примеры

    Четвертичные графы: определение, свойства и примеры (K5, граф Хватала). В теории графов – графы, где степень каждой вершины равна 4.

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

  56. Coxeter graph

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

  57. Paley graph

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