Содержание
15 отношения: NP-полная задача, Колесо (теория графов), Планарный граф, Род поверхности, Стягивание ребра, Топология, Теорема Понтрягина — Куратовского, Теорема Робертсона — Сеймура, Минор графа, Изоморфизм графов, Барицентрическое подразделение, Вершина (теория графов), Гамильтонов граф, Глоссарий теории графов, Гомеоморфизм.
- Теория графов
NP-полная задача
NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных).
Посмотреть Гомеоморфизм графов и NP-полная задача
Колесо (теория графов)
В теории графов колесом Wn называется граф с n вершинами (n ≥ 4), образованный соединением единственной вершины со всеми вершинами (n-1)-цикла.
Посмотреть Гомеоморфизм графов и Колесо (теория графов)
Планарный граф
Плана́рный граф — граф, который может быть изображён на плоскости без пересечения рёбер.
Посмотреть Гомеоморфизм графов и Планарный граф
Род поверхности
Поверхность рода 0 Поверхность рода 1 Поверхность рода 2 Поверхность рода 3 Род поверхности — топологическая характеристика замкнутой ориентируемой поверхности \Sigma, такое число g, что данная поверхность гомеоморфна сфере с g ручками.
Посмотреть Гомеоморфизм графов и Род поверхности
Стягивание ребра
Стягивание ребра между помеченными вершинами. В теории графов стягивание ребра — это операция, которая удаляет ребро из графа, а до этого связанные ребром вершины сливаются в одну вершину.
Посмотреть Гомеоморфизм графов и Стягивание ребра
Топология
Лента Мёбиуса — поверхность с одной стороной и одним краем; пример объекта, изучаемого в топологии. бублика и кружки. Тополо́гия (от τόπος — место и λόγος — слово, учение) — раздел математики.
Посмотреть Гомеоморфизм графов и Топология
Теорема Понтрягина — Куратовского
Теорема Понтрягина — Куратовского или Теорема Куратовского — теорема в теории графов, дающая необходимое и достаточное условие планарности графа.
Посмотреть Гомеоморфизм графов и Теорема Понтрягина — Куратовского
Теорема Робертсона — Сеймура
Теорема Робертсона — Сеймура (также называемая теоремой о минорах графа) утверждает, что неориентированные графы, частично упорядоченные отношением минорности, образуют множество.
Посмотреть Гомеоморфизм графов и Теорема Робертсона — Сеймура
Минор графа
В теории графов неориентированный граф H называется минором графа G, если H может быть образован из G удалением рёбер и вершин и стягивания рёбер.
Посмотреть Гомеоморфизм графов и Минор графа
Изоморфизм графов
В теории графов изоморфизмом графов G.
Посмотреть Гомеоморфизм графов и Изоморфизм графов
Барицентрическое подразделение
Четырёхкратное барицентрическое подразделение треугольника. Барицентри́ческое подразделе́ние симплициального комплекса — определённый тип подразделения комплекса на более мелкие симплексы.
Посмотреть Гомеоморфизм графов и Барицентрическое подразделение
Вершина (теория графов)
Граф с 6 вершинами и 7 рёбрами, в котором вершина с номером 6 в левом верхнем углу — лист, или висячая вершина В теории графов вершиной называется фундаментальная единица, образующая графы — неориентированный граф состоит из множества вершин и множества рёбер (неупорядоченных пар вершин), в то время как ориентированный граф состоит из множества вершин и множества дуг (упорядоченных пар вершин).
Посмотреть Гомеоморфизм графов и Вершина (теория графов)
Гамильтонов граф
Гамильтонова линия для додекаэдра, предложенная Гамильтоном для замены его игры «вокруг света» на додекаэдре на задачу для плоского графа. Гамильто́нов граф — математический объект теории графов.
Посмотреть Гомеоморфизм графов и Гамильтонов граф
Глоссарий теории графов
Здесь собраны определения терминов из теории графов.
Посмотреть Гомеоморфизм графов и Глоссарий теории графов
Гомеоморфизм
тор топологически эквивалентны Гомеоморфи́зм (ὅμοιος — похожий, μορφή — форма) — взаимно однозначное и взаимно непрерывное отображение топологических пространств.
Посмотреть Гомеоморфизм графов и Гомеоморфизм
См. также
Теория графов
- Вершина (теория графов)
- Выпуклый подграф
- Гипотеза Эрдёша — Бура
- Глоссарий теории графов
- Гомеоморфизм графов
- Граф (математика)
- Граф Петерсена
- Дискретный оператор Лапласа
- Доминатор (теория графов)
- Задача о семи кёнигсбергских мостах
- Изоморфизм графов
- Икосиан
- Икосианы
- Инвариант графа
- Магический граф
- Наследственное свойство
- Ориентированный граф
- Парадокс дружбы
- Петля (теория графов)
- Раскраска графов
- Случайный граф
- Степень вершины (теория графов)
- Структурная индукция
- Теория графов
- Тотальная раскраска
- Транзитивное сокращение
- Характеризация запрещёнными графами
- Цепь Маркова
Также известен как Подразделение графа.