Квиток 15 теорія Знакові графи
Знаковий граф-це граф, вершини які відповідають членам груп. Дуги між вершинами позначаються знаками "+" та "-". Знак + означає, що відносини між учасниками добрі, знак “-“ погані. Якщо знаки між вершинами відсутні, це означає, що між учасниками ставлення байдужості. Приклад:
Визначення збалансованості групи: Група N що складається з n учасників є збалансованою, якщо її можна розбити на 2 підгрупи N1 і N2, такі що всі учасники всередині груп ставляться позитивно один до одного або байдужі, а будь-які два учасники з різних груп перебувають у антипатії друг до друга.
Визначення збалансованого знакового графа: знаковий граф збалансований, якщо безліч його вершин можна розбити на 2 групи, у кожній з яких відносини описуватимуться “+” , а будь-які дві взяті вершини з різних груп будуть зі знаком “-“ .
Приклад збалансованого графа:
Даний граф збалансований, оскільки є дві множини N1, N2: N1 = [a, b, c]; N2=[e,d] у яких відносини мають знак “+” а між будь-якими вершинами різних груп відносини описуються знаком “-“.
Критерій збалансованості графа: Введемо поняття циклу, як знака твору дуг, що входять до нього. Дуга, що входить до цього циклу зі знаком «+» матиме коефіцієнт =+1, дуга зі знаком -, матиме коефіцієнт зі знаком -1. Таким чином, граф збалансований, якщо будь-який цикл входить до нього буде позитивним.
Міра збалансованості графа:
С + = число позитивних простих циклів, С - число всіх простих циклів. (Простий цикл - в якому початкова вершина збігається з кінцевим)
Приклад знаходження міри збалансованості:
