Расчет веса графа

[Soul Friend]

Условия:
1) Ориентированное ребро графа весит 1 и обозначается стрелкой -> и показывает направление A -> B, из вершины A в B но не обратно.
2) Неориентированное ребро весит 2 и обозначается "ромбом" -<>- пример A -<>- B в обе стороны.
3) Граф должен быть связным, из любой вершины можно пройти в любую другую вершину.
4) Радиус графа не должен превышать 3 (максимальное расстояние между вершинами должно быть 3),
то есть из одной вершины в другой разрешено строить не больше 3 ребер, ориентированное или нет по усмотрению.

Задача построить граф, из $n$ вершин, с наименьшим количеством веса (сложить веса ребер).
Пример для $n=2$ две вершины А -<>-B вес 2.
Пример для $n=3$ три вершины А -> B -> C -> А - вес 3.
Пример для $n=4$ четыре вершины А -> B -> C -> D -> A - вес 4.
Пример для $n=5$ пять вершин А -<>- B -> C -<>- D -<>- E -<>-A - вес 9.

Есть ли формула расчета для $n$ вершин ? Хочу создать программу на Python но не знаю как строить расчеты.
Может машинное обучение подключить? Но данных мало, может на OEIS есть последовательность ?

[dgwuqtj]

При $n = 5$ пример не работает, из $D$ в $C$ кратчайший путь длины 4.

[Soul Friend]

dgwuqtj

dgwuqtj в сообщении #1668914 писал(а):

При $n = 5$ пример не работает, из $D$ в $C$ кратчайший путь длины 4.

Да, просчитался, исправил.

[dgwuqtj]

Если уж писать программу, то можно просто перебрать все графы на фиксированном множестве из $n$ вершин. Есть пример с $2 n - 3$ рёбрами при $n \geq 3$: соединим первые три вершины в ориентированный треугольник, а также соединим одну из них со всеми остальными неориентированными рёбрами. Всего графов с $\leq 2 n - 4$ рёбрами ровно $\binom {n^2 - n} 0 + \ldots + \binom{n^2 - n}{2 n - 4}$. При $n = 11$ эта сумма равна $669\,240\,664$, что даже на Питоне по идее перебирается.

Или есть основания предполагать, что там имеется красивая формула для произвольного $n$?

[Soul Friend]

dgwuqtj в сообщении #1668923 писал(а):

Или есть основания предполагать, что там имеется красивая формула для произвольного $n$?

Об этом я и интересуюсь, есть ли точная формула или как рассчитать без перебора.

dgwuqtj в сообщении #1668923 писал(а):

а потом первые 3 вершины соединим в ориентированный треугольник.

то есть больше одного цикла с тремя вершинами (и с ориентированными ребрами ) не получится построить ?

[пианист]

Можно еще к mip свести и подтянуть, соответственно, какую-то библиотечку, типа or-tools.
Правда, реально вряд ли оно считать будет, в смысле, для сколько-то больших чисел.

[dgwuqtj]

Soul Friend в сообщении #1668928 писал(а):

то есть больше одного цикла с тремя вершинами (и с ориентированными ребрами ) не получится построить ?

У меня не получилось. Я сначала думал, что у меня есть пример на $2 n - 4$ ребра, но там была ошибка.

[Soul Friend]

Soul Friend в сообщении #1668910 писал(а):

Пример для $n=5$ пять вершин А -<>- B -> C -<>- D -<>- E -<>-A - вес 9.

есть вес поменьше А -<>- B ; A -<>- C ; A -<>- D ; D -<>- E - общий вес 8.
для $n=6$ у меня получается наименьший вес 10.

[mihaild]

Написал кривой код на ortools https://colab.research.google.com/drive ... sp=sharing.
Для $n = 5$ нашелся вес 7.

Вложение:

download (1).png [ 22.32 Кб | Просмотров: 0 ]

Для $n = 6$ - 9.

Вложение:

download (2).png [ 9.8 Кб | Просмотров: 74 ]

Но это собственно решение dgwuqtj, только вместо неориентированного ребра к центральной вершине, присоединяем новую к ребру треугольника.

Для $n = 7$, судя по скорости, за разумное время в текущем виде не посчитает, надо хоть немного оптимизировать.

[Soul Friend]

mihaild
Скормил ваш код в ChatGPT, теперь выводит результат в localhost через streamlit в 3D :
7 вершин посчитал быстро, а вот при расчете 8-ми вершин думал несколько минут.
3D он выводит быстро, а вот вывод в 2D тормозит и занимает время.
И вариантов могут быть несколько. У меня для 6 вершин с весом 9 получился другой граф.

(Код)

import streamlit as st
import networkx as nx
import numpy as np
from ortools.linear_solver import pywraplp
import plotly.graph_objects as go
import matplotlib.pyplot as plt

def calculate_and_draw(N):
    # Создание оптимизационной задачи
    solver = pywraplp.Solver.CreateSolver("SAT")

    # Переменные путей
    paths = {
        (i, j, p): solver.IntVar(0, 1, f"path{p}_{i}_{j}")
        for p in range(1, 4)
        for i in range(N)
        for j in range(N)
        if i != j
    }

    # Переменные для путей через вершину k
    ptk = {}
    for i in range(N):
        for j in range(N):
            if i != j:
                for p in [2, 3]:
                    path_through_k = {
                        k: solver.IntVar(0, 1, f"path{p}_{i}_{k}_{j}")
                        for k in range(N)
                        if k not in [i, j]
                    }
                    ptk[(i, j, p)] = path_through_k

                    # Добавляем ограничения
                    for k, v in path_through_k.items():
                        solver.Add(paths[(i, k, p - 1)] + paths[(k, j, 1)] >= 2 * v)
                    solver.Add(
                        paths[(i, j, p)]
                        <= sum(v for k, v in path_through_k.items())
                        + paths[(i, j, p - 1)]
                    )

                solver.Add(1 <= paths[(i, j, 3)])

    # Целевая функция: минимизация количества рёбер
    solver.Minimize(
        sum(paths[(i, j, 1)] for i in range(N) for j in range(N) if i != j)
    )

    # Решение задачи
    status = solver.Solve()
    if status != pywraplp.Solver.OPTIMAL:
        st.error("Не удалось найти оптимальное решение.")
        return

    # Вывод минимального веса
    min_weight = solver.Objective().Value()
    st.write(f"Минимальный вес: {min_weight}")

    # Построение графа на основе решения
    G = nx.DiGraph()

    # Добавляем вершины
    for i in range(N):
        G.add_node(i)

    # Списки рёбер для графики
    edges_oriented = []
    edges_bidirectional = []

    # Добавляем рёбра
    for i in range(N):
        for j in range(N):
            if i != j:
                # Ориентированные рёбра
                if paths[(i, j, 1)].solution_value() == 1:
                    G.add_edge(i, j)
                    edges_oriented.append((i, j))
                # Неориентированные рёбра (учитываем два направления)
                if paths.get((i, j, 1)) and paths.get((j, i, 1)):
                    if paths[(i, j, 1)].solution_value() == 1 and paths[(j, i, 1)].solution_value() == 1:
                        if (j, i) not in edges_bidirectional:
                            edges_bidirectional.append((i, j))

    # Генерация координат для вершин
    pos = {
        i: (
            np.cos(2 * np.pi * i / N),
            np.sin(2 * np.pi * i / N),
            0.5 * (i % 2),
        )
        for i in range(N)
    }

    # 3D график с использованием Plotly
    fig = go.Figure()

    # Отображение ориентированных рёбер (синим цветом с стрелками)
    for edge in edges_oriented:
        x = [pos[edge[0]][0], pos[edge[1]][0]]
        y = [pos[edge[0]][1], pos[edge[1]][1]]
        z = [pos[edge[0]][2], pos[edge[1]][2]]
        fig.add_trace(go.Scatter3d(
            x=x, y=y, z=z, mode='lines+text',
            line=dict(color='blue', width=4),
            text=[f"{edge[0]} → {edge[1]}"],
            textposition="top center"
        ))

    # Отображение неориентированных рёбер (зелёным цветом)
    for edge in edges_bidirectional:
        x = [pos[edge[0]][0], pos[edge[1]][0]]
        y = [pos[edge[0]][1], pos[edge[1]][1]]
        z = [pos[edge[0]][2], pos[edge[1]][2]]
        fig.add_trace(go.Scatter3d(
            x=x, y=y, z=z, mode='lines+text',
            line=dict(color='green', width=4),
            text=[f"{edge[0]} ↔ {edge[1]}"],
            textposition="top center"
        ))

    # Отображение вершин
    for node, (x, y, z) in pos.items():
        fig.add_trace(go.Scatter3d(
            x=[x], y=[y], z=[z], mode='markers+text',
            marker=dict(size=10, color='red'),
            text=[str(node)],
            textposition="bottom center"
        ))

    fig.update_layout(
        title="Минимальный граф с радиусом ≤ 3",
        scene=dict(
            xaxis_title='X',
            yaxis_title='Y',
            zaxis_title='Z'
        ),
        showlegend=False
    )

    # Отображение интерактивного 3D графика
    st.plotly_chart(fig)

    # 2D график с использованием NetworkX
    fig_2d, ax = plt.subplots(figsize=(8, 6))

    # Попробуем использовать стандартное положение для рёбер
    pos_2d = nx.circular_layout(G)  # Используем круговую раскладку для 2D

    # Построение 2D-графика
    nx.draw(G, pos_2d, with_labels=True, node_size=500, node_color='red', font_size=16, font_color='white', edge_color='blue', width=2, arrows=True)

    # Отображение 2D графика
    st.pyplot(fig_2d)


# Интерфейс Streamlit
st.title("Минимизация веса графа с ограничениями")

# Поле для ввода количества вершин
N = st.number_input("Введите количество вершин (N)", min_value=2, step=1)

# Кнопка для расчета
if st.button("Рассчитать"):
    calculate_and_draw(N)