Note de curs, probleme algoritmică, 28 octombrie 2013

From Algopedia
Revision as of 12:45, 3 November 2013 by Dan (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

În acest curs am discutat despre problema Ciclu Eulerian.

Cerința

Dându-se un graf (neorientat, multigraf) să se determine dacă admite un ciclu eulerian și să se identifice un astfel de ciclu.

Un ciclu eulerian este un ciclu care conține toate muchiile grafului exact o dată.

Existența

Un graf admite un ciclu eulerian dacă și numai dacă (1) gradele tuturor nodurilor sale sunt pare și (2) nodurile (cu grad nenul) sunt conexe.

Demonstrație intuitivă a condiției de existență

Dacă nodurile cu grad nenul ale grafului nu sunt conexe, atunci nu există un drum care să conțină muchii din două componente conexe distincte. Cu atât mai puțin, nu poate exista un ciclu care să conțină toate muchiile grafului.

Dacă există un ciclu eulerian asociat unui graf, atunci de fiecare dată când ciclul va trece printr-un nod al grafului va folosi două muchii incidente cu respectivul nod. Astfel, toate nodurile grafului vor avea un număr par de muchii incidente (toate nodurile vor avea un grad par).

Construirea unui ciclulu eulerian

(1) Pornind dintr-un nod cu grad nenul, se construiește un lanț, fără a repeta muchii, prin parcurgerea în adâncime a grafului, până se va atinge un nod fără muchii incidente nefolosite. Deoarece toate nodurile au grad par, se va obține un ciclu.

Ciclul obținut conține, obligatoriu, toate muchiile incidente cu nodul din care am pornit.

(2) Parcurgând ciclul obținut inițial, de fiecare dată când ajungem într-un nod cu muchii incidente care nu fac parte din ciclu, folosind metoda descrisă la pasul (1) obținem un nou ciclu care, obligatoriu, conține toate aceste muchii. Se va integra noul ciclu în ciclul inițial și se va continua parcurgerea sa.

La sfârșitul parcurgerii, deoarece graful este conex, se vor fi vizitat toate nodurile cu grade nenule. Deoarece au fost vizitate toate nodurile cu grade nenule, s-au integrat în ciclul inițial toate muchiile grafului, obținându-se astfel un ciclu eulerian.

Grafuri orientate, neorientate și multigrafuri

În cazul grafurilor neorientate, graful trebuie să aibă toate nodurile cu grad par.

În cazul grafurilor orientate, graful trebuie să aibă toate nodurile cu gradul intern egal cu gradul extern.

În cazul multigrafurilor trebuie să parcurgem o muchie de mai multe ori și să ciclăm în unele noduri.

Implementarea algoritmului

Pentru memorarea grafului se vor folosi liste de adiacență, fiind un graf rar. Pentru a putea diferenția între muchiile folosite și cele nefolosite, acestea vor fi stocate folosind o structură:

const int MAX_N = 100000;
const int MAX_M = 500000;

struct Edge {
	int vertex1;
	int vertex2;
	bool used;
};

int N, M;
vector<Edge*> Neighbours[MAX_N + 1];

Trebuie remarcat faptul că listele de adiacență sunt memorate sub forma unui vector de vectori de pointeri către muchiile adiacente. Deoarece aceeași muchie este referită în ambele liste de adiacență ale nodurilor care o definesc, atunci când ea este marcată ca folosită într-una din liste, implicit apare ca folosită și în cealaltă.

Ciclurile vor fi memorate ca liste simplu înlănțuite. Mai mult, pentru a fi ușor de integrat cu alte cicluri, pentru un ciclu se va memora atât primul nod cât și ultimul:

struct ListNode {
	int vertex;
	ListNode* nextListNode;
};

struct List {
	ListNode *firstNode;
	ListNode *lastNode;
};

Două operații frecvent utilizate în algoritm vor fi:

  • să se determine dacă un nod dat mai are muchii incidente nefolosite;
  • să se găsească un vecin adiacent unui nod dat (printr-o muchie nefolosită);
  • să se construiască un ciclu care conține toate muchiile incidente cu un nod dat;
  • să se afișeze nodurile unui ciclu dat.

Pentru aceste operații se vor implementa funcțiile:

bool hasNeighbour(int vertex);

int nextNeighbour(int vertex);

List getCycle(int vertex);

void printList(List cycle);

O implementare incompletă a algoritmului este prezentată în continuare:

#include <stdio.h>
#include <vector>

using namespace std;

const int MAX_N = 100000;
const int MAX_M = 500000;

struct Edge {
	int vertex1;
	int vertex2;
	bool used;
};

struct ListNode {
	int vertex;
	ListNode* nextListNode;
};

struct List {
	ListNode *firstNode;
	ListNode *lastNode;
};

int N, M;
vector<Edge*> Neighbours[MAX_N + 1];

bool cycleExists;

bool hasNeighbour(int vertex);

int nextNeighbour(int vertex);

List getCycle(int vertex) {
	List answer;
	answer.firstNode = new ListNode();
	answer.firstNode->vertex = vertex;
	answer.firstNode->nextListNode = NULL;

	ListNode* currentNode = answer.firstNode;
	int currentVertex = vertex;
	ListNode* nextNode;
	int nextVertex;
	while (hasNeighbour(currentVertex)) {
		nextVertex = nextNeighbour(currentVertex);
		nextNode = new ListNode();
		nextNode->vertex = nextVertex;
		nextNode->nextListNode = NULL;
		currentNode->nextListNode = nextNode;
		currentNode = nextNode;
		currentVertex = nextVertex;
	}

	answer.lastNode = currentNode;
	return answer;
}

void printList(List cycle);

int main(void) {
	int i;
	int a, b;
	Edge* edge;

	// citirea datelor
	scanf("%d %d", &N, &M);
	for (i = 0; i < M; ++i) {
		scanf("%d %d", &a, &b);
		edge = new Edge();
		edge->vertex1 = a;
		edge->vertex2 = b;
		edge->used = false;
		Neighbours[a].push_back(edge);
		Neighbours[b].push_back(edge);
	}

	// calcularea solutiei
	cycleExists = true;
	for (i = 1; i <= N; ++i) {
		if (Neighbours[i].size() % 2 == 1) {
			cycleExists = false;
		}
	}

	List cycle;
	if (cycleExists) {
		cycle = getCycle(1);
		// step (2) goes here
	}

	// afisarea solutiei
	if (cycleExists) {
		printList(cycle);
	} else {
		printf("-1\n");
	}
	return 0;
}