симметричный граф без изолированных вершин является вершинно-транзитивным, и любой вершинно-транзитивный граф является регулярным. Однако не все вершинно-транзитивные...

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

связи вершин граф-схемы алгоритма: например, если в граф-схеме алгоритма имеет место альтернативное ветвление, начинающееся условной вершиной a ψ {\displaystyle...

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

{\displaystyle k} -связный граф (вершинно k {\displaystyle k} -связный) — это связный граф, который: имеет больше k {\displaystyle k} вершин; остаётся связным после...

Дистанционно-транзитивный граф (англ. distance-transitive graph) — граф, в котором любая упорядоченная пара вершин переводится в любую другую упорядоченную...

соответствующие вершинам графа (над полем чисел {0, 1}). Граф называется вершинно-транзитивным если он имеет симметрии, которые переводят любую вершину в любую...

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

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

это наименьший гипогамильтонов граф. Как конечный связный вершинно-транзитивный граф, не имеющий гамильтонова цикла, граф Петерсена является контрпримером...

1959 году, а также Стивеном Уоршеллом в 1962 году для поиска транзитивного замыкания графа, и тесно связан с алгоритмом Клини (опубликовано в 1956 г.)...

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

Например, любой турнир с семью вершинами содержит транзитивный турнир с тремя вершинами. Турнир Пэли с семью вершинами показывает, что это максимум, что...

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

имеется в точности один источник и один сток. Любой транзитивный турнир является биполярным. Любой граф имеет ациклическую ориентацию. Одним из способов...

Ориентированный граф (орграф) называется сильно связным (англ. strongly connected), если любые две его вершины s и t сильно связны, то есть если существует...

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

Полусимметричный граф — неориентированный рёберно-транзитивный регулярный граф, не являющийся вершинно-транзитивным. Другими словами, граф полусимметричен...

порядке. Графы сравнимости также называют транзитивно-ориентируемыми графами, частично упорядочиваемыми графами и графами вложенности. Граф несравнимости —...

любую вершину в любую другую, графы призм являются вершинно-транзитивными графами. Являясь полиэдральными графами, эти графы также являются вершинно 3-связными...

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

{\displaystyle u,v\in V(G).} Вершинно-транзитивные графы являются графами регулярных блужданий. Полусимметричные графы являются графами регулярных блужданий....

число графа G равно вершинному хроматическому числу его рёберного графа L(G). Рёберный граф рёберно-транзитивного графа является вершинно-транзитивным графом...

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

ориентированного графа с тем же набором вершин и с теми же дугами, но ориентация дуг этого графа противоположна ориентации дуг графа G. То есть, если граф G содержит...

теории графов любое бинарное отношение R на X можно понимать как ориентированный граф (V, A), где V = X — это вершины и A = R — дуги графа. Транзитивное сокращение...

рёберно-транзитивным графом, но не вершинно-транзитивным графом регулярной степени 3. Такие графы называются полусимметричными кубическими графами. Фактически...

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

произведение является вершинно-транзитивным графом тогда и только тогда, когда каждое из его множителей является вершинно-транзитивным. Декартово произведение...

достижимости простого ориентированного графа G = ( V , A ) {\displaystyle G=(V,A)}  — бинарная матрица замыкания по транзитивности отношения A {\displaystyle A}...

графа G тогда и только тогда существует гомоморфизм в транзитивный турнир с k вершинами, когда не существует гомоморфизма из пути с (k + 1) вершинами...