Двудольный граф

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Двудольный граф

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

Определение[править | править код]

Полный двудольный граф

Неориентированный граф называется двудольным, если множество его вершин можно разбить на две части , так, что

  • ни одна вершина в не соединена с вершинами в и
  • ни одна вершина в не соединена с вершинами в .

В этом случае, подмножества вершин и называются долями двудольного графа .

Связанные определения[править | править код]

Двудольный граф называется полным двудольным (это понятие отлично от полного графа; то есть, такого, в котором каждая пара вершин соединена ребром), если для каждой пары вершин существует ребро . Для

такой граф обозначается символом .

Примеры[править | править код]

Двудольные графы естественно возникают при моделировании отношений между двумя различными классами объектов. К примеру граф футболистов и клубов, ребро соединяет соответствующего игрока и клуб, если игрок играл в этом клубе. Более абстрактные примеры двудольных графов:

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

Свойства[править | править код]

  • Граф является двудольным тогда и только тогда, когда он не содержит цикла нечётной длины.
    • В частности двудольный граф не может содержать клику размером более 2.
  • Граф является двудольным тогда и только тогда, когда он 2-раскрашиваем; то есть его хроматическое число равняется двум.
  • Граф разбивается на пары разноцветных вершин тогда и только тогда, когда любые элементов одной из долей связаны по крайней мере с элементами другой (Теорема о свадьбах).
  • Полный двудольный граф, у которого в каждой части больше 2 вершин, является непланарным.
  • Любой двудольный граф является совершенным.

Проверка двудольности[править | править код]

Проверка двудольности с помощью чётности расстояний

Для того, чтобы проверить граф на предмет двудольности, достаточно в каждой компоненте связности выбрать любую вершину и помечать оставшиеся вершины во время обхода графа (например, поиском в ширину) поочерёдно как чётные и нечётные (см. иллюстрацию). Если при этом не возникнет конфликта, все чётные вершины образуют множество , а все нечётные — .

Алгоритм решения:

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

Основываясь на этом свойстве при поиске в ширину можно вычёркивать вершины которые помечаются двумя цветами.

Проблемы:

1) Начав с «плохой» вершины можно получить плохой вариант, в нашем примере это №3

2) Не подходит для поиска с критериями

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

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

После чего мы образуем связи между этими группами, и характеризуем связи нужным критерием. Этот метод не является жадным алгоритмом , так как он проводит анализ всех узлов в целом.

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

Пример реализации в коде:


let index = 1;

export class Node{
  links : Node[] = [];
    id: number;
    constructor(){
        this.id = index++;
    }
}

import { Node } from './node';

export type GroupLinks = {group: Group, links: number};
export class Group {
    nodes: Node[] = [];
    groups: GroupLinks[] = [];
    isCorrect(node: Node) {
        const linked: boolean[] = this.nodes.map(n => n.links.indexOf(node) >= 0);
        return linked.indexOf(true) === -1;
    }
    addNode(node: Node) {
        if (!this.isCorrect(node))
            return false;
        this.nodes.push(node);
        for (let obj of this.groups) {
            const check = obj.group.nodes.map(n => n.links.indexOf(node) >= 0);
            //console.log(1,obj.group.nodes,'|',node);
            const add = check.indexOf(true) === -1?0:1;
            obj.links += add;
            let self = this;
            obj.group.groups.forEach(g=>{
                if(g.group == self)
                    g.links += add;
            });
        }
        return true;
    }
}

import { Node } from './node';


const MATRIX = [];

const NODE_COUNT = ///;

const nodes: Node[] = [];
for (let i = 0; i < NODE_COUNT; i++) {
    nodes.push(new Node());
}
for (let i = 0; i < NODE_COUNT; i++) {
    for (let j = 0; j < NODE_COUNT; j++) {
        if(MATRIX[i][j] !== 1)
            continue;
        nodes [i].links.push(nodes [j]);
    }
}
export {nodes};


Применения[править | править код]

См. также[править | править код]