Abstract:

Հավասարակշռված երկմաս կողմնորոշված գրաֆի կողմնորոշված ցիկլը կոչվում է նախահամիլտոնյան, եթե այն պարունակում է այդ գրաֆի բոլոր գագաթները ( բացի երկուսից: Ներկա աշխատանքում ցույց է տրվում հետևյալ պնդումը. Թեորեմ: Դիցուք' Թ-ն 2a > 10 գագաթանի հավասարակշռված երկմաս կողմնորոշված գրաֆ է: Եթե այդ գրաֆի գագաթների ցանկացած հաղթող զույգի առնվազն մեկ գագաթի լոկալ աստիճանը փոքր չէ 2a — 2 թվից, ապա Թ-ն պարունակում է նախահամիլտոնյան ցիկլ կամ Թ-ի չկողմնորոշված հիմք գրաֆը 2 -կապակցված է կամ Թ-ն իզոմորֆ է մեկ 10 գագաթանի գրաֆին:
; Ориентированный контур проходящий через все вершины сбалансированного двудольного орграфа, кроме двух вершин, называется предгамильтоновым контуром. В настоящей статье доказывается: Теорема: Пусть Б - 2а-вершинный (а > 5) сбалансированный двудольный орграф. Если для любых доминирующих пар вершин по крайней мере одна вершина имеет локальную степень не меньше чем 2а — 2, то Б содержит предгамильтоновый контур или неориентированная основа граф орграфа является Б 2-связной или Б изоморфен одному орграфу с десятью вершинами.

Identifier:

oai:noad.sci.am:136050