|
Архив публикацийТезисыXV-ая конференцияО локально-сбалансированных 2-разбиениях некоторых двудольных графовАрмения, 0038, г. Ереван, ул. Шинарарнер 10/1, кв 118 2 стр.В работе рассматриваются неориентированные связные графы без кратных ребер и петель [1]. Множество вершин графа G обозначается через V(G), множество ребер – через E(G). Максимальная из степеней вершин графа G обозначается через . Для положим . 2-разбиением графа G называется функция . 2-разбиение f графа G называется локально-сбалансирован-ным1, если для , (1) 2-разбиение f графа G называется локально-сбалансированным2, если для , (2) В [2] доказана NP-полнота задачи о существовании локально-сбалансированного1 2-разбиения для двудольных графов G с . В [3] доказана NP-полнота задачи о существовании локально-сбалансированного2 2-разбиения для двудольных графов G с . Задачи о существовании и построении таких 2-разбиений актуальны, поскольку они соответствуют задачам о таком распределении влияний двух противоположных сил, которое уменьшает вероятность конфликтов. Субъекты модели-руемой системы могут обладать или не обладать способностью самозащиты, в связи с чем при моделировании нужно следовать, соответственно, определению (2) или (1). Пусть A – множество графов, в которых любые два простых цикла [1] имеют не более одной общей вершины. В работе получено необходимое и достаточное условие существования локально-сбалансированного1 2-разбиения двудольных графов класса A. |
