Supprimer degré deux sommets d'un graphe non orienté (Skiena TADM 5-22)

Question

A partir du Manuel de conception algorithme, 2ème édition, question 5-22:

Concevoir un algorithme temps linéaire pour éliminer chaque sommet v degré 2 à partir d'un graphique en remplaçant les bords (u, v) et (v, w) par un bord (u, w). Nous cherchons également à éliminer plusieurs copies d'arêtes en les remplaçant par un seul arête. Notez que la suppression de plusieurs copies d'une arête peut créer un nouveau sommet de degré 2, qui doit être supprimé, et que la suppression d'un sommet de degré 2 peut créer plusieurs arêtes, qui doivent également être supprimées.

Parce que la question apparaît dans la section sur les graphes non orientés, supposer que notre graphe est non orienté.

Voici un algorithme permettant de supprimer les sommets de degré deux comme souhaité, similaire à celui donné here. L'implémentation repose sur les structures de graphe, de file d'attente et d'édgenode de Skiena. g-> edges [v] est un pointeur vers la tête de la liste d'adjacence de v. g-> M [u] [v] renvoie la valeur booléenne dans la ligne u et la colonne v de la matrice d'adjacence de g. Le problème: selon mon analyse, cela ne fonctionne pas en temps linéaire, que nous utilisions des listes d'adjacence ou des matrices d'adjacence pour représenter notre graphe.

process_vertex(graph *g, int v, queue Q) { 
    int u,w; 
    if (degree[v] != 2) {return;} 

    u = pop_first_edge(g,v); // O(n) for AL, O(n) for AM 
    w = pop_first_edge(g,v); // O(n) for AL, O(n) for AM 
    if (!edge_exists(g,u,w)) { // O(n) for AL, O(1) for AM 
     insert_edge(g,u,w); 
    } 

    if (degree[u] == 2) {enqueue(Q,u);} 
    if (degree[w] == 2) {enqueue(Q,w);} 
} 

remove_degree_twos(graph *g) { 
    queue Q; 
    for (int v = 1; v <= g->nvertices; ++v) { 
     if (degree[v] == 2) {enqueue(Q,v);} 
    } 
    while (!Q.empty()) { 
     process_vertex(g,dequeue(Q),Q); 
    } 
} 

Il y a deux fonctions nécessaires qui n'ont pas encore été mises en œuvre:

// removes the first edge in v's adjacency list 
// and updates degrees appropriately 
// returns the vertex to which that edge points 
int pop_first_edge(g,v); 

// determines whether edge (u,v) already exists 
// in graph g 
bool edge_exists(g,u,v); 

Si g est représenté avec des listes de contiguïté, peut alors être mis à exécution les fonctions requises comme suit:

// O(n) 
int pop_first_edge(g,v) { 
    int u = -1; // the vertex to which the first outedge from v points 
    edgenode *p = g->edges[v]; 

    if (p != NULL) { 
     u = p->y; 
     g->edges[v] = p->next; 
     --(g->degree[v]); 

     // delete v from u's adjacency list 
     p1 = &g->edges[u]; 
     p2 = g->edges[u]; 
     while (p2 != NULL) { 
      if (p2->y == v) { 
       *p1 = p2->next; 
       --(g->degree[u]); 
       break; 
      } 
      p1 = p2; 
      p2 = p2->next; 
     } 
    } 
} 

// O(n) 
edge_exists(g,u,w) { 
    edgenode *p = g->edges[u]; 

    while (p != NULL) { 
     if (p->y == w) { 
      return true; 
     } 
     p = p->next; 
    } 

    return false; 
} 

Si g est représenté avec des matrices d'adjacence, alors nous avons:

// O(n) 
int pop_first_edge(v) { 
    int u = -1; 

    for (int j = 1; j <= g->nvertices; ++j) { 
     if (M[v][j]) { 
      u = j; 
      break; 
     } 
    } 

    if (u > 0) { 
     M[v][u] = false; 
     M[u][v] = false; 
     --(g->degree[v]); 
     --(g->degree[u]); 
     return u; 
    } else { 
     return -1; 
    } 
} 

// O(1) 
edge_exists(g,u,w) { 
    return g->M[u][w]; 
} 

Que nous utilisions des listes d'adjacence ou des matrices d'adjacence, l'exécution de process_vertex est O (n), où n est le nombre de sommets dans le graphe. Comme les sommets O (n) peuvent être traités, le temps d'exécution total est O (n^2).

Comment cela peut-il être fait en temps linéaire?

Answer 1

Supposons que nous ayons graphe G = (V, E), où

V={1,...,n} 

est un ensemble de sommets et E est un ensemble d'arêtes, sous-ensemble par conséquent de jeu

{(x,y) : x,y in V} 

Habituellement, le graphique est donné par la liste des bords. Supposons que nous le recevions de cette façon.Maintenant:

1. font l'ensemble des arêtes distinctes (O (m), m = | E |), considérer les bords (x, y) et (y, x) égale à
2. créer un tableau représentant la degré de chaque sommet de G (O (m) à nouveau)
3. pour chaque sommet v de degré 2 faire une liste de ces 2 arêtes (ce qui est O (m), une itération sur les bords est suffisant)
4. enfin itérer sur les sommets de degré 2 et remplacer les arêtes liées par un bord se débarrasser du sommet de degré 2 (c'est opération O (n))
5. répéter l'étape 1. et retour des bords

Code VOICI écrit en python:

def remove_2_degree_vertices(n, edges): 

    adj_matrix = [[0]*n for i in xrange(n)] 

    #1 O(m) 
    edges = get_distinct(adj_matrix, edges) 

    #2 O(m) 
    degrees = calculate_degrees(n, edges) 

    #3 O(m) 
    adj_lists = get_neighbours(degrees, edges) 

    #4 O(n + m) 
    to_remove, to_add_candidates = process(n, adj_lists)  
    edges.extend(to_add_candidates) 
    result = [(e0,e1) for e0, e1 in edges if to_remove[e0][e1] == 0] 

    #5 O(m) 
    adj_matrix = [[0]*n for i in xrange(n)] 
    result = get_distinct(adj_matrix, result) 

    return result 

def get_distinct(adj_matrix, edges): 
    result = [] 
    for e0, e1 in edges: 
     if adj_matrix[e0][e1] == 0: 
      result.append((e0,e1)) 
      adj_matrix[e0][e1] = adj_matrix[e1][e0] = 1 
    return result 


def calculate_degrees(n, edges): 
    result = [0]*n 
    for e0, e1 in edges: 
     result[e0] += 1 
     result[e1] += 1 
    return result 


def get_neighbours(degrees, edges): 
    result = {} 
    for e0, e1 in edges: 
     if degrees[e0] == 2: 
      add_neighbour(result, e0, e1) 
     if degrees[e1] == 2: 
      add_neighbour(result, e1, e0) 
    return result 


def add_neighbour(neighbours, key, value): 
    if not neighbours.has_key(key): 
     neighbours[key] = set() 
     neighbours[key].add(value) 
    else: 
     neighbours[key].add(value) 


def process(n, adj_lists): 
    to_remove = [[0 for i in xrange(n)] for j in xrange(n)] 
    to_add_candidates = [] 

    if len(adj_lists) == 0: 
     return to_remove, to_add_candidates 

    for key in adj_lists: 
     neighbours = list(adj_lists[key]) 
     if len(neighbours) == 1: 
      to_remove[key][neighbours[0]] = to_remove[neighbours[0]][key] = 1 
     else: # len(neighbours) == 2 
      remove_edge(adj_lists, to_remove, key, neighbours[0], neighbours[1]) 
      remove_edge(adj_lists, to_remove, key, neighbours[1], neighbours[0]) 
      to_add_candidates.append((neighbours[0], neighbours[1])) 

    return to_remove, to_add_candidates 


def remove_edge(adj_lists, to_remove, key, n0, n1): 
    to_remove[key][n0] = to_remove[n0][key] = 1 
    if n0 in adj_lists: 
     adj_lists[n0].remove(key) 
     adj_lists[n0].add(n1)