Голова быка (теория графов)

Голова быка — планарный неориентированный граф с 5 вершинами и 5 рёбрами в форме треугольника с двумя непересекающимися висячими рёбрами.

Хроматическое число графа равно 3, хроматический индекс равен 3, радиус 2, диаметр 3 и обхват 3. Граф является блоковым, расщепляемым, интервальным графом без клешней, вершинно 1-связным и рёберно 1связным.

Источник: Википедия

Связанные понятия

В теории графов доминирующее множество рёбер (или рёберное доминирующее множество) графа G = (V, E) — это подмножество D ⊆ E, такое, что любое ребро не из D смежно по меньшей мере одному ребру из D. На рисунках (a)–(d) приведены примеры доминирующих множеств рёбер (красные рёбра).

Бабочка имеет диаметр 2 и обхват 3, радиус 1, хроматическое число 3, хроматический индекс 4 и является как эйлеровым, так и графом единичных расстояний. Граф является вершинно 1-связным графом и рёберно 2-связным.

Граф дружеских отношений (или граф датской мельницы, или n-лопастной вентилятор) Fn — это планарный неориентированный граф с 2n+1 вершинами и 3n рёбрами.

Преобразование треугольник-звезда — способ эквивалентного преобразования пассивного участка линейной электрической цепи — «треугольника» (соединения трёх ветвей, которое имеет вид треугольника, сторонами которого являются ветви, а вершинами — узлы), в «звезду» (соединение трёх ветвей, которые имеют один общий узел). Эквивалентность «треугольника» и «звезды» обусловлена тем, что при одинаковых напряжениях между одноименными выводами электрической цепи токи, которые втекают в одноименные выводы, а...

Блоковый многогранник — это (многомерный) многогранник, образованный из симплекса путём многократного приклеивания другого симплекса к одной из его фасет.

Однозначно раскрашиваемый граф — это k-цветный граф, допускающий только одну (правильную) k-раскраску (с точностью до перестановки цветов).

Флаг в геометрии многогранников — последовательность граней (различной размерности) абстрактного многогранника, в которой каждая предыдущая грань содержится в последующей и последовательность содержит ровно по одной грани каждой размерности.

Гипотеза Эрдёша-Бура — математическая проблема, касающаяся числа Рамсея на разреженных графах.

Говорят, что семейство графов имеет ограниченное расширение, если все его миноры ограниченной глубины являются редкими графами. Много естественных семейств редких графов имеют ограниченное расширение. Близкое, но более сильное свойство, полиномиальное расширение, эквивалентно существованию теорем разбиения для этих семейств. Семейства с этими свойствами имеют эффективные алгоритмы для задач, в которые входят задача поиска изоморфного подграфа и проверка моделей для теории первого порядка для графов...

Подробнее: Ограниченное расширение графа

Апейрогон (от др.-греч. ἄπειρος — бесконечный или безграничный и др.-греч. γωνία — угол) — обобщённый многоугольник со счётно-бесконечным числом сторон.

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

Говорят, что ориентированный граф апериодичен, если нет целого числа k > 1, делящего длину любого цикла графа. Эквивалентно, граф апериодичен, если наибольший общий делитель длин его циклов равен единице. Этот наибольший общий делитель для графа G называется периодом графа G.

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

Подробнее: Число наклонов графа

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

Подробнее: Спичечный граф

В геометрии конциклическими (или гомоциклическими) точками называют точки, находящиеся на одной окружности. Три точки на плоскости, не лежащие на одной прямой, всегда лежат на одной окружности, поэтому иногда термин «конциклические» прилагают только к наборам из 4 или более точек.

Подробнее: Конциклические точки

Самодополнительный граф — это граф, изоморфный своему дополнению. Простейшие нетривиальные самодополнительные графы — это путь, состоящий из 4 вершин и цикл из 5 вершин.

В геометрии правильный косой многогранник — это обобщение множества правильных многогранников, которое включает возможность непланарных граней или вершинных фигур. Коксетер рассматривал косые вершинные фигуры, которые создавали новые четырёхмерные правильные многогранники, а много позднее Бранко Грюнбаум рассматривал правильные косые грани.

Почти многоугольник — это геометрия инцидентности, предложенная Эрнестом Е. Шультом и Артуром Янушкой в 1980. Шульт и Янушка показали связь между так называемыми тетраэдрально замкнутыми системами прямых в евклидовых пространствах и классом геометрий точка/прямая, которые они назвали почти многоугольниками. Эти структуры обобщают нотацию обобщённых многоугольников, поскольку любой обобщённый 2n-угольник является почти 2n-угольником определённого вида. Почти многоугольники интенсивно изучались, а...

Плосконосая квадратная антипризма — это один из многогранников Джонсона (J85, М28 по Залгаллеру).

Неориентированный граф G двойственно хордален, если гиперграф его максимальных клик является гипердеревом. Имя происходит из факта, что граф хордален тогда и только тогда, когда гиперграф его максимальных клик двойственен гипердереву. Первоначально эти графы были определены по максимальному соседству и имеют ряд различных описаний. В отличие от хордальных графов свойство двойственной хордальности не наследуется, то есть, порождённые подграфы двойственного хордального графа не обязательно двойственно...

Жёсткость графа — мера связности графа: граф G t-жёсток при некотором вещественном t, если для любого целого k > 1 нельзя разбить граф G на k различных компонент связности путём удаления менее чем tk вершин. Например, граф 1-жёсток, если число компонент, образующихся при удалении вершин, всегда не превосходит числа удалённых вершин. Жёсткость графа — это максимальное t, для которого он t-жёсток. Число является конечным числом для всех конечных графов, за исключением полных графов, которые, по соглашению...

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

В теории графов снарки «Цветы» образуют бесконечное семейство снарков, введённых Айзексом Руфусом в 1975 году.

Подробнее: Снарк «Цветок»

Многогранник, многоугольник или мозаика является изотоксальным или рёберно транзитивным, если его симметрии действуют транзитивно на его рёбрах. Неформально это означает, что имеется только один вид рёбер у объекта — если даны два ребра, существует параллельный перенос, вращение и/или зеркальное отражение, переводящее одно ребро в другое, не меняя область, занимаемую объектом.

Подробнее: Изотоксальная фигура

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

Гипе́рбола Ки́перта — гипербола, определяемая по данному треугольнику. Если последний представляет собой треугольник общего положения, то эта гипербола является единственным коническим сечением, проходящим через его вершины, ортоцентр и центроид.

В теории графов полная раскраска — это противоположность гармонической раскраске в том смысле, что это раскраска вершин, в которой каждая пара цветов встречается по меньшей мере на одной паре смежных вершин. Эквивалентно, полная раскраска — это минимальная раскраска, в том смысле, что её нельзя преобразовать в правильную раскраску с меньшим числом цветов путём слияния двух цветов. Ахроматическое число ψ(G) графа G — это максимальное число цветов среди всех полных раскрасок графа G.

Наибольший многоугольник единичного диаметра — многоугольник с n сторонами (для заданного числа n), диаметр которого равен единице (то есть любые две его точки находятся друг от друга на расстоянии, не превосходящем единицы), и имеющий наибольшую площадь среди других n-угольников диаметра единица. Решением (не уникальным) для n = 4 является квадрат, решением для нечётных n является правильный многоугольник, при этом для остальных чётных n правильный многоугольник наибольшим не будет.

В теории графов двусвязный граф — это связный и неделимый граф, в том смысле, что удаление любой вершины не приведёт к потере связности. Теорема Уитни утверждает, в частности, что граф двусвязен тогда и только тогда, когда между любыми двумя его вершинами есть минимум два реберно непересекающихся пути. Таким образом, двусвязный граф не имеет шарниров.

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

Гипотеза Тёплица, также известная как гипотеза о вписанном квадрате — нерешённая проблема геометрии. Формулировка гипотезы...

Интервальная размерность графа — это минимальная размерность, в которой заданный граф может быть представлен в виде графа пересечений гиперпрямоугольников (то есть многомерных прямоугольных параллелепипедов) с параллельными осям рёбрами. То есть должно существовать один-к-одному соответствие между вершинами графа и множеством гиперпрямоугольников, таких, что прямоугольники пересекаются тогда и только тогда, когда существует ребро, соединяющее соответствующие вершины.

Ромботриаконтáэдр( от греч. τριάκοντα (греч. τριάντα) — «тридцать» и εδρον — «грань») — выпуклый тридцатигранник с одинаковыми ромбическими гранями. Относится к каталановым телам. Является двойственным по отношению к икосододекаэдру и зоноэдром.

Подробнее: Ромботриаконтаэдр

Идеальный треугольник — треугольник в геометрии Лобачевского, все три вершины которого являются идеальными, или бесконечно удалёнными, точками. Идеальные треугольники иногда называют трижды асимптотическими треугольниками. Их вершины иногда называют идеальными вершинами. Все идеальные треугольники равны.

Ориентированная раскраска графа — это специальный вид раскраски графов. А именно, это назначение цветов вершинам ориентированного графа, которое...

В геометрии двойная шестёрка Шлефли — это конфигурация из 30 точек и 12 прямых, предложенная Шлефли. Прямые конфигурации можно разделить на два подмножества по 6 прямых, при этом каждая прямая не пересекается (то есть, скрещивается) с прямыми одного множества и пересекается с каждой прямой другого ). Каждая из 12 прямых конфигурации имеет 5 точек пересечения, и каждая из этих 30 точек пересечения принадлежит ровно двум прямым, принадлежащим разным подмножествам, так что двойная шестёрка Шлефли обозначается...

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

Подробнее: Рёберно-транзитивный граф

Теорема Понтрягина — Куратовского, или теорема Куратовского, — теорема в теории графов, дающая необходимое и достаточное условие планарности графа.

Для ориентированного графа G термины converse (обратный), transpose (транспонированный) или reverse (противоположный) используются для обозначения другого ориентированного графа с тем же набором вершинам и с теми же дугами, но ориентация дуг этого графа противоположна ориентации дуг графа G. То есть, если граф G содержит дугу (u,v), то обратный/транспонированный/противоположный граф графу G содержит дугу (v,u) и наоборот.

Подробнее: Транспонированный граф

Слабая раскраска — это специальный вид разметки графа. Слабая k-раскраска графа G = (V, E) назначает цвета c(v) ∈ {1, 2, ..., k} всем вершинам v ∈ V, так что каждая неизолированная вершина смежна по меньшей мере одной вершине другого цвета. В формальных обозначениях, для любой неизолированной вершины v ∈ V существует вершина u ∈ U с {u, v} ∈ E и c(u) ≠ c(v).

При визуализации графов, когда рёбра графа представляются ломаными (последовательностью отрезков, соединённых в точках излома), желательно минимизировать число изломов на ребро (что иногда называется сложностью кривой) или общее число изломов на рисунке. Минимизация изломов — это алгоритмическая задача поиска рисунка графа, минимизирующего указанные величины.

Подробнее: Минимизация изломов

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

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

Подробнее: Граф единичных кругов

В теории графов свободный от t-биклик граф — это граф, в котором нет полных двудольных графов с 2t вершинами Kt,t в качестве подграфов. Семейство графов является свободным от биклик, если существует число t, такое, что все графы в семействе свободны от t-биклик. Семейства свободных от бициклов графов образуют одно из наиболее общих типов семейств разреженных графов. Они возникают в задачах инцидентности в комбинаторной геометрии, а также используются в теории параметрической сложности.

Лексикографический поиск в ширину (англ. lexicographic breadth-first search, LBFS or Lex-BFS) — алгоритм упорядочивания вершин графа. Алгоритм отличается от алгоритма поиска в ширину и дает более упорядоченную последовательность вершин графа.

k-Смежностный многогранник — это выпуклый многогранник, в котором любое k-элементное подмножество его вершин является множеством вершин некоторой грани этого многогранника.

Равносторонний многоугольник — многоугольник, у которого все стороны равны. Например, равносторонний треугольник — это треугольник, у которого все три стороны одинаковы; все равносторонние треугольники подобны и имеют внутренние углы 60 градусов. Равносторонний четырёхугольник — это ромб, и квадрат является частным случаем ромба.

(Топологический) индекс Хосойи, известный также как Z индекс, графа — это полное число паросочетаний на нём. Индекс Хосойи всегда больше либо равен одному, поскольку пустое множество рёбер считается как паросочетание. Эквивалентно, индекс Хосойи — это число непустых паросочетаний плюс один.

Универсальный граф — это бесконечный граф, содержащий любой конечный (или не более чем счётный) граф в качестве порождённого подграфа. Универсальный граф этого типа первым построил Р. Радо и этот граф теперь называется графом Радо или случайным графом. Более свежие работы фокусируются на универсальных графах для семейства графов F. То есть бесконечный граф, принадлежащий F, содержащий все конечные графы семейства F. Например, графы Хэнсона являются универсальными в этом смысле для графов без i-клик...

Большой ромбогексаэдр — это невыпуклый однородный многогранник. Двойственным ему является большой ромбогексакрон. Вершинная фигура — самопересекающийся четырёхугольник.

а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я