Ask a graph theory algorithm

wangyanping

I just looked at some network flow problems, mainly for the capacity of the edge, and this problem can be regarded as the capacity of the node.

Or is there any way in the network flow to solve this problem? Please enlighten me

dommionr

Towangyanping():
When K becomes very large, it is unrealistic. The best detection method should be to find the number of simple paths, as long as there is exactly one =K-2*n(n>=0)

zhangjk

if

      5----6
　　／　　　　／｜
　／　　　　／　｜
１－－－－2　　｜
｜　　 　｜　　八
｜　　　　｜　／
｜　　　　｜／
3---4　

How many disjoint simple paths are there between 3-6?

不一般的魔

As shown:
    4----------5
   /| /|
  / | / |
0--|-------1 |
| | | |
| 6-------|--7
| / | /
|/ |/
2----------3

Find: the path from 0 to 1

#include <iostream.h>

const int MAX = 8;

//Create a matrix corresponding to the picture
int num[MAX][MAX]={{1,1,1,0,1,0,0,0}, {1,1,0,1,0,1,0,0},{1,0 ,1,1,0,0,1,0},
{0,1,1,1,0,0,0,1},{1,0,0,0,1,1,1,0},{0,1,0,0,1,1,0 ,1},{0,0,1,0,1,0,1,1},
{0,0,0,1,0,1,1,1}};

/**
   Detect the possibility of repeated cycles
   */
bool test(int s[], int length, int key)
{
for(int i=0; i<length; i++)
{
if(s[i] == key)
return false;
}
return true;
}

/**
   start: starting point
   end: end
   */
void Search(int start, int end)
{
int top = 0;
int d[MAX]={0};
int s[MAX] = {0};
bool is = true;
d[top] = start;

while(top> -1)
{
is = true;
while(s[d[top]]++ <MAX)
{
if(d[top] != s[d[top]]-1&&num[d[top]][s[d[top]]-1] == 1)
{
if(s[d[top]]-1 == end) //Find the output path
{
for(int i=0; i<=top; i++)
{
cout<<d[i]<<'';
}
cout<<end<<endl;
}
else
{
if(test(d, top, s[d[top]]-1))
{
top++;
d[top] = s[d[top-1]]-1;
s[d[top]] = 0;
is = false;
break;
}
}
}
}
if(is == true)
{
top--; //Rewind
}
}
}

void main()
{
Search(0,1); //Find the path from 0 to 1
}

Output result:
0 1
0 2 3 1
0 2 3 7 5 1
0 2 3 7 6 4 5 1
0 2 6 4 5 1
0 2 6 4 5 7 3 1
0 2 6 7 3 1
0 2 6 7 5 1
0 4 5 1
0 4 5 7 3 1
0 4 5 7 6 2 3 1
0 4 6 2 3 1
0 4 6 2 3 7 5 1
0 4 6 7 3 1
0 4 6 7 5 1
Press any key to continue

wangyanping

zhangjk: There are two paths between 3-6

wangyanping

bigc: I didn't realize that K may be very large for the Google question. But your algorithm may have problems in the following figure:

1－－－－2－－－－3－－－－4
        /\|\
       5---6 7--

37 is a loop of length 2 and 256 is a loop of length 3. Then take k=22 to solve

wangyanping

bigc: find the 22 o'clock path between 1-4

zhangjk

Find the largest number of disjoint simple paths between two points in 2 steps:
1. Find all the simple paths between two points (regardless of intersection and disjoint);
2. From all simple paths, find the largest disjoint path subset.

wangyanping

This can be done using network streaming methods.

The nodes in this graph except uv are decomposed into T into two nodes T1 and T2, and T1 only inherits those edges whose end point is T, T2 only inherits edges whose starting point is T, and there is an edge between T1 and T2. This will generate a new graph, and set the capacity of each edge to 1, so that it can be calculated

520520520

A similar question:
Given a set of vertex pairs (ui, vi), how to connect them as much as possible (ui connects vi), and the paths do not intersect

More practical questions:
ui, vi are points on the plane, how to connect them on this plane with straight line segments, the paths do not intersect, and the line segments have width