English
!

Архив публикаций

Тезисы

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.



© 2004 Дизайн Лицея Информационных технологий №1533