将图修正为欧拉图

Question

我试图制作一个uni项目，生成具有给定值的图，并使其成为欧拉图（如果不是），但假定的固定图仍然具有奇数度顶点。请帮我找到问题。可能在FixGraph（）中。它正在重复这些内容有点，但仍然没有完全解决问题（有些事实仍然很奇怪）。

using System;
using System.Collections.Generic;

public class Graph
{
    private int V;   // No. of vertices
    private List<int>[] adj; // Array of lists for Adjacency List Representation
    private Random rand;

    // Constructor
    public Graph(int v)
    {
        V = v;
        adj = new List<int>[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new List<int>();
        rand = new Random();
    }

    // Function to add an edge into the graph
    public void addEdge(int v, int w)
    {
        adj[v].Add(w);// Add w to v's list.
        adj[w].Add(v); //The graph is undirected
    }

    // Function to generate the graph based on probability
    public void GenerateGraph(double probability)
    {
        for (int i = 0; i < V; i++)
        {
            for (int j = i + 1; j < V; j++)
            {
                if (rand.NextDouble() < probability)
                {
                    addEdge(i, j);
                }
            }
        }
    }

    // Function to display the adjacency matrix
    public void DisplayAdjacencyMatrix()
    {
        Console.WriteLine("Adjacency Matrix:");
        for (int i = 0; i < V; i++)
        {
            for (int j = 0; j < V; j++)
            {
                if (adj[i].Contains(j))
                    Console.Write("1 ");
                else
                    Console.Write("0 ");
            }
            Console.WriteLine();
        }
    }

    // A function used by DFS
    private void DFSUtil(int v, bool[] visited)
    {
        // Mark the current node as visited
        visited[v] = true;

        // Recur for all the vertices adjacent to this vertex
        foreach (int neighbor in adj[v])
        {
            int n = neighbor;
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }

    // Method to check if all non-zero degree vertices are connected. It mainly does DFS traversal starting from
    private bool IsConnected()
    {
        // Mark all the vertices as not visited
        bool[] visited = new bool[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;

        // Find a vertex with non-zero degree
        int j;
        for (j = 0; j < V; j++)
            if (adj[j].Count != 0)
                break;

        // If there are no edges in the graph, return true
        if (j == V)
            return true;

        // Start DFS traversal from a vertex with non-zero degree
        DFSUtil(j, visited);

        // Check if all non-zero degree vertices are visited
        for (int k = 0; k < V; k++)
            if (!visited[k] && adj[k].Count > 0)
                return false;

        return true;
    }

    // Function to fix the graph by connecting vertices with odd degrees
    public void FixGraph()
    {
        // Find vertices with odd degree
        List<int> oddVertices = new List<int>();
        for (int i = 0; i < V; i++)
        {
            if (adj[i].Count % 2 != 0)
                oddVertices.Add(i);
        }

        // Connect vertices with odd degree
        for (int i = 0; i < oddVertices.Count; i += 2)
        {
            if (i + 1 < oddVertices.Count)
                addEdge(oddVertices[i], oddVertices[i + 1]);
        }
    }

    // Method to run test cases
    public void Test()
    {
        DisplayAdjacencyMatrix();
        int res = IsEulerian();
        if (res == 0)
        {
            Console.WriteLine("Graph is not Eulerian, fixing it...");
            FixGraph();
            Console.WriteLine("Fixed graph:");
            DisplayAdjacencyMatrix();
        }
        else if (res == 1)
            Console.WriteLine("Graph has an Euler path");
        else
            Console.WriteLine("Graph has an Euler cycle");
    }

    // Method to check if the graph is Eulerian
    private int IsEulerian()
    {
        // Check if all non-zero degree vertices are connected
        if (!IsConnected())
            return 0;

        // Count vertices with odd degree
        int odd = 0;
        for (int i = 0; i < V; i++)
            if (adj[i].Count % 2 != 0)
                odd++;

        // If count is more than 2, then graph is not Eulerian
        if (odd > 2)
            return 0;

        // If odd count is 2, then semi-eulerian.
        // If odd count is 0, then eulerian
        // Note that odd count can never be 1 for undirected graph
        return odd == 2 ? 1 : 2;
    }

    // Driver method
    public static void Main(string[] args)
    {
        // Let us create and test graphs
        int vertices = 10;
        double probability = 0.5; // Adjust the probability as needed

        Graph g = new Graph(vertices);
        g.GenerateGraph(probability);
        g.Test();

        // Displaying edges
        Console.WriteLine("\nEdges:");
        for (int i = 0; i < vertices; i++)
        {
            foreach (var neighbor in g.adj[i])
            {
                if (i < neighbor)
                    Console.WriteLine($"{i}  {neighbor}");
            }
        }
    }
}

互联网上的一切

Answer 1

for (int i = 0; i < oddVertices.Count; i += 2)

您假设有偶数个奇数顶点。如果没有，那么最后一个奇数顶点将不会被固定。