Reputation: 21
Assume I have a number list, where each element is a vertex of an undirected weighted graph (with possible loops) and the element's value is the vertex degree. I want to develop an algorithm which runs through all possible combinations of edges for such list of vertices. In other words, I want to get all possible adjacency matrices.
Besides, two vertices with same degree would be different, so in Python's realization it would rather be a dict (im python code monkey, so im sorry for this explanation). And there are no isolated vertices.
The set can be realized as a graph by condition (is graphic).
Within my very poor abilities, the only very crude and general solution I managed to develop is to
Sort all vertices numerically by degree (just for clarity. E.g. {A:2, B:1, C:3} -> {B:1, A:2, C:3})
Create the list of all possible edges (just routine combinatorics)
2.1) If have a vertex deg>1, there could be loops, and they should be generated additionally. And i (still seems feasible: {B:1, A:2, C:3} -> {(B, A), (B, C), (A, A), (A, C), (C, C)}) *there is another problem that there may be two BC edges, or if deg>=4 there may be two loops on one vertex, but my alorithm should take it into account
Group the edges into sets in a way that each vertice must be present in the set as many times as it corresponds to its degree. And here's beginning something i cannot sort out. Seems like quite sophisticated combinatorics... For example,
3.1) Add a special counter for each vertex which traces how many times this vertex is used in current graph, which trace the condition if the vertex is fully occupied in the current graph
Run a loop over the edges set, dragging each edge meeting the condition (vertex counter < vertex degree). End of loop == "counting" all the vertices (therefore i can run through the set more than once and collect all necessary edges, e.g. two BC). So in the end I must get a correct graph with all vertices occupied properly, but the main question is...
How to start the next loop? I can just start each new for loop with n+1 edge. But im not sure if i get truly all possible graphs. I'm trying to solve it, and i would greatly appreciate any external comment. Maybe, there is some alorithm validation or the opposite, or some completely different, way more effective solution for this problem. Thanks in advance
P.S. I've revised Erdos–Gallai theorem and Havel–Hakimi algorithm, but AFAIC it only can tell if the list of vertices is graphic. And i need a little bit more)
Upvotes: 1
Views: 53