алгоритм "разделяй и властвуй" для нахождения трехцветного треугольника в неориентированном графе со следующими свойствами?

Question

В неориентированном графе G = (V, E) вершины окрашены в красный, желтый или зеленый цвет. Кроме того, существует способ разбить граф на два подмножества так, чтобы | V1 | = | V2 | или | V1 | = | V2 | +1, где применяются следующие условия: либо каждая вершина V1 связана с каждой вершиной V2, либо ни одна вершина V1 не связана с вершиной V2. Это относится рекурсивно ко всем индуцированным подграфам V1 и V2

Я могу найти все треугольники в Графе, умножив матрицу смежности на себя три раза и увеличивая узлы, соответствующие ненулевым элементам главной диагонали. Затем я вижу, правильно ли окрашены узлы треугольника. O (п ^ ~ 2,8)! Но учитывая уникальные свойства графа, я хочу найти решение, используя разделяй и властвуй, чтобы найти цветной треугольник. это пример графа с заданными свойствами. Мне нужно найти жирный треугольник: Синие прямоугольники означают, что перегородки полностью соединены, фиолетовые - отсутствие связи между перегородками

Answer 1

Это можно сделать в O(E*V) без использования свойства partition.Начните с удаления всех ребер с одинаковым цветом в обеих вершинах, это можно сделать в O(E).На модифицированном графике G' каждый треугольник представляет собой трехцветный треугольник.Поиск треугольников на графике:

for each edge e(u,v):
    for each vertex w:
        if e(v,w) and e(u,w) in G':
            add (u,v,w) to triangle list

Если вы сохраняете список смежности, а также матрицу смежности, вы можете улучшить время внутреннего цикла, проверив только w в списке смежности v.В этом случае сложность составляет O(E * max(deg(v)).

Answer 2

Постановка задачи:

Найти все треугольники в неориентированном графе с вершинами разных цветов.(Красный, желтый и зеленый).

Допущения:

Существует способ разбить график на два подмножества так, чтобы | V1 | = | V2 |или | V1 | = | V2 | +1, где применяются следующие условия: либо каждая вершина V1 связана с каждой вершиной V2, либо ни одна вершина V1 не связана с вершиной V2.Это относится рекурсивно ко всем индуцированным подграфам V1 и V2.

Логика:

Мы можем рекурсивно разбить граф на два подграфа и найти треугольник, образованный между одной вершиной вV1 и две другие в V2 или одна вершина в V2 и две другие в V1.

При каждом рекурсивном вызове мы можем разбить данный граф на V1, V2, который будет удовлетворять вышеуказанному свойству (разделение функции уже дано),Рекурсия прерывается, когда размер V1, V2 становится равным нулю или оба становятся равными 1. Эта функция вызывается рекурсивно как для V1, так и для V2.Если между V1 и V2 нет ребра, нам не нужно рассматривать это разбиение для нашего окончательного списка треугольников;поэтому мы возвращаемся с этого звонка.

Теперь для каждой вершины в V2 мы добавляем в глобально объявленную карту цветов для трех цветовых комбинаций.Используя эту карту, для каждой вершины в V2 мы проверяем соответствующую другую цветовую комбинацию и добавляем ее в список треугольников.

Псевдо реализации

//let g be the given graph.
//Vertex be the class representing each vertex ( will have attributes 'vertex_number' + 'colour')
//let Edge be the class representing edges ( will have attributes 'a' and 'b' corresponding to two edges
//let (v1,v2) = partition(g) be the given function which can partition the graph into V1, v2.
//let adjacency_list be the ArrayList<ArrayList<Vertex>> containing the Adjacency list for the given vertices


//Main Callee Method
HashMap<String, List<Edge>> edge_list = new HashMap<String, List<Edge>>()
ArrayList<ArrayList<Vertex>> adjacency_list = new ArrayList<ArrayList<Vertex>>()
edge_list.put('rg', new ArrayList<Edge>())
edge_list.put('gy', new ArrayList<Edge>())
edge_list.put('yr', new ArrayList<Edge>())
ArrayList<new ArrayList<Vertex>> triangle_list = new ArrayList<new ArrayList<Vertex>>()
getColouredTriangles(g)


//Recursive Implementation of Coloured Triangle method
getColouredTriangles(g):
    (v1,v2) = partition(g)
    //If size is zero or both have size as 1 no triangles can be formed
    if v1.size() == 0 || v2.size() == 0 || (v1.size() == 1 && v2.size() == 1):
        return

    //Calling recursively for both v1 and v2
    getColouredTriangles(v1)
    getColouredTriangles(v2)

    //If there is no edge between the two subgraphs, return as no triangle is possible now between v1 and v2.
    if not edge(v1.get(0), v2.get(0)):
        return
    //call for one vertex in v1, two in v2
    getTrianglesInTwoGraphs(v1,v2)
    //call for one vertex in v2, two in v1
    getTrianglesInTwoGraphs(v2,v1)

//Method to get triangles between two graphs with one vertex in v1 and other two in v2.
getTrianglesInTwoGraphs(v1,v2):
    //Form edge_list having colour to Edge mapping
    for v in v2:
        for vertex in adjacency_list.get(v):
            if vertex in v2:
                String colour = v.colour + vertex.colour
                if(edge_list.get(colour) == null):
                    colour = vertex.colour + v.colour
                edge_list.colour.put(colour,vertex.edge)

    //for each v in v1, check other coloured edges from edge_list
    for v in v1:
        ArrayList<Edge> edges = new ArrayList<Edge>()
        if v.colour == r:
            edges = edge_list.get("gy")
        else if v.colour == g:
            edges = edge_list.get("yr")
        else:
            edges = edge_list.get("rg")
        for edge in edges:
            ArrayList<Vertex> vertices = new ArrayList<Vertex>()
            vertices.add(v)
            vertices.add(edge.a)
            vertices.add(edge.b)
            triangle_list.add(vertices)

Результат:

Глобальная переменная triangle_list содержит группы вершин с цветными треугольниками.