Phần 1: Kiểm tra có tồn tại chu trình hay đường đi euler không?

29/10/2017

Hii,chào mừng các bạn đến với phần tiếp theo của phần hiện thực các phương thức liên quan đến đồ thị.Hôm nay,chúng ta đến với phần tương đối căng não một chút.(hihi đùa đó,không khó lắm đâu).

Vì phần phân tích bài này khá dài,nên Phong sẽ tách ra làm 2 phần,phần 1 (là phần các bạn đang đọc nè),phần này Phong nói về cách kiểm tra một đồ thị có đường đi,hoặc chu trình euler hay không?Phần 2 là phần Phong nói về cách phân tích,viết thuật toán tìm ra đường đi,hoặc chu trình euler.

Đối với bài toán về euler ta cần phải tìm hiểu xem euler là cái gì?Chu trình nó là gì?Đường đi là sao?...Đến đây thì ta đi search wiki và trả lời nhanh thôi.Hehe

Đây đây,cái khái niệm khó hiểu đây:
Trong lý thuyết đồ thị, một đường đi trong đồ thị G=(X,E) được gọi là đường đi Euler nếu nó đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần. Đường đi Euler có đỉnh cuối cùng trùng với đỉnh xuất phát gọi là chu trình Euler.

Chi tiết chút nữa nè:
Đường đi Euler (tiếng Anh: Eulerian path, Eulerian trail hoặc Euler walk) trong đồ thị vô hướng là đường đi của đồ thị đi qua mỗi cạnh của đồ thị đúng một lần (nếu là đồ thị có hướng thì đường đi phải tôn trọng hướng của cạnh).
Chu trình Euler (tiếng Anh: Eulerian cycle, Eulerian circuit hoặc Euler tour) trong đồ thị vô hướng) là một chu trình đi qua mỗi cạnh của đồ thị đúng một lần và có đỉnh đầu trùng với đỉnh cuối.

Hii,đọc câu trên mà ai tìm ra điều kiện để có đường đi hoặc chu trình ngay lặp tức thì bài này dễ như trở bàn tay luôn ý.hehe.Chúng ta đến với phần dễ hiểu để áp dụng nhé!Các bạn tập trung vào định lý của nó.

1.Một đa đồ thị không có điểm cô lập có chu trình Euler nếu và chỉ nếu đồ thị là liên thông và mỗi đỉnh của nó đều có bậc chẵn
2.Đồ thị vô hướng liên thông G=(X, E) có đường đi Euler khi và chỉ khi G có đúng hai đỉnh bậc lẻ . Nếu G có hai đỉnh bậc lẻ thì đường đi Euler có hai đầu đường đi nằm ở hai đỉnh bậc lẻ.
3.Đồ thị có hướng liên thông G=(X, E) có chu trình Euler, khi đó: số đỉnh bậc trong của G sẽ bằng số đỉnh bậc ngoài của G (d+(x) = d-(x),∀xϵ X).
4.Cho G=(V,E) có hướng, không có đỉnh cô lập. Và |V|>1. G có đường đi Euler nhưng không có chu trình Euler G liên thông yếu và có đúng 2 đỉnh x,y thoả:
deg+(x)=deg-(x)+1
deg-(y)=deg+(y)+1 .
Các đỉnh còn lại cân bằng.

Đó,nhìn vào định lý có thể dễ cho lập trình rồi nè.Đối với vô hướng,ta nhìn định lý 1 xem.Đó là thứ giúp ta có thể kiểm tra khi nào thì đồ thị có chu trình euler,và với định lý 2 giúp ta biết khi nào thì có đường đi euler.

Ta bắt đầu phân tích nhé,với chu trình.Ta nhìn lại định lý 1.Nó có chu trình khi nào các bạn?Có phải là khi đồ thị toàn là đỉnh bậc chẵn và nó liên thông thì ok không.Mà ở bài tính bậc của đồ thị và bài kiểm tra liên thông mình đã có một mớ phương thức hỗ trợ rồi còn gì.Có phải là ta duyệt tất cả đỉnh của đồ thị và đếm bậc của đỉnh (bằng phương thức topdegree(i)) nếu nó có một cái lẽ là false ngay lập tức không,nếu điều kiện trên thõa cùng với nó là liên thông thì trả về là true.ok không nè.heehe.Dễ không nè.
Tiếp theo nha,nhìn vào định lý 2:Bạn thấy nó khác câu trên gì không,chỉ khác là ta đếm xem trong đồ thị có bao nhiêu đỉnh bậc lẽ.Nếu có 2 thì nó có đường đi,lớn hơn 2 thì nó không có đường đi.Đó,tuyệt vời ông mặt trời luôn.Hehe.

Đó là ý tưởng,giờ mình phân tích code xem thế nào nhé:

Hiện thực kiểm tra chu trình euler:

@Override
	public boolean checkHasEulerCycle() {
	//biến kiểm tra đỉnh có thỏa điều kiện ở định lý 1 không
		boolean okTop = true;
		//Biến kiểm tra đồ thị có liên thông không
		boolean okCon = checkConnected();
		//duyệt đồ thị và kiểm tra cứ có thằng nào lẽ là false ngay
		for (int i = 0; i < matrixA.length; i++) {
			if (topDegree(i) % 2 != 0) {
				okTop = false;
			}
		}
		// Nếu như 2 biến này true hết thì ok rồi nè
		if (okCon && okTop ) {
			return true;
		}
		return false;
	}

Đường đi euler có khi nào?

@Override
	public boolean checkHasEulerPath() {
	//Ở đây khá tương tự,biến đếm số đỉnh bậc lẽ
		int count = 0;
		//kiểm tra tính liên thông
		boolean okCon = checkConnected();
		//DUyệt đồ thị và đếm 
		for (int i = 0; i < matrixA.length; i++)
			if (topDegree(i) % 2 != 0)
				count++;
        //Nếu tổng số đỉnh bậc lẽ của đồ thị mà bằng 2 và đồ thị liên thông thì đưa ra kết luận ok 
		if (count == 2 && okCon)
			return true;
		return false;
	}

Ôi,mới có cái vô hướng mà nó dài lòng thòng ghê hồn luôn.Hehe,giờ mình tới có hướng nè.Có hướng chúng ta cũng phân tích tương tự nhé!

Đối với chu trình,ta xem định lý 3,nó nói rằng chỉ cần đồ thị liên thông và tất cả các đỉnh phải có bậc ra bằng bậc vào (nó giống giống với vô hướng đó bạn,thật ra là số đỉnh bậc chẵn để thể hiện rằng nó có thể vào và ra đỉnh đó chỉ lập lại đỉnh và không lập lại cạnh,ở đây có hướng thì nó nói là vào = ra luôn nè).Hii, đến đây thì thấy thuật toán luôn ời,ta có phương thức tính bậc ra bậc vào rồi,chỉ việc if else nó bằng nhau là true hay false thôi.Phải hông nè?Xem code bên dưới nè:

@Override
	public boolean checkHasEulerCycle() {
		// neu co bac ra ma khong bang voi bac vao thi false luôn
		for (int i = 0; i < matrixA.length; i++) {
			if (topDegreeIn(i) != topDegreeOut(i))
				return false;
		}
		// neu dieu kien tren dung thi xet them tinh lien thong 
		// vì liên thông mạnh chứa liên thông yếu theo tính logic nên ta dùng dấu hoặc trong if nhé
		if ((checkConectedWeakly() || checkConectedStrongly()))
			return true;
		return false;
	}

OK rồi,đến ngay tới cái cúng cuồi thôi,hehe.Kiểm tra có đường đi euler ở đồ thị có hướng hay không?

Dựa ngay vào cái định lý còn lại thôi,khi đọc định lý này ta thấy ngay nó có 3 điều kiện,1 là liên thông yếu,2 là phải thỏa có đúng 2 đỉnh có tính chất bậc vào thì bằng bậc ra +1 (tức là vào nhỏ hơn ra 1 đơn vị) và đỉnh còn lại có bậc ra bằng bậc vào +1 (tức là ra lớn hơn vào 1 đơn vị). Và cuối cùng là các đỉnh còn lại phải cân bằng.Đấy.Khá là đơn giản.Giờ ta lập trình ngay thôi,hehe.

@Override
	public boolean checkHasEulerPath() {
		int count = 0;
		int canBang = 0;
		//đoạn này max dễ hiểu luôn nè,các bạn nghiệm từ từ nhé
		for (int i = 0; i < matrixA.length; i++) {
			// co duy nhat 2 dinh co dieu kien
			if (topDegreeIn(i) == (topDegreeOut(i) + 1) || topDegreeOut(i) == (topDegreeIn(i) + 1)) {
				count++;
			}
			// cac dinh con lai phai can bang
			if (topDegreeIn(i) == topDegreeOut(i)) {
				canBang++;
			}
		}
		// lien thong yeu va thoa 2 dieu kien tren,cái cân bằng đương nhiên là phải bằng số đỉnh đồ thị 
// trừ cho 2 đỉnh thỏa điều kiện trên.Điều này khá dễ hiểu phải hông nè. if (checkConectedWeakly() && count == 2 && canBang == (topNum() - 2)) return true; return false; }

Bài viết này khá dài,bạn nào đọc được tới đây thì thật là không phải dạng vừa đâu,hihi.Các bạn quả thật là người siêng năng đó.Chúc các bạn làm hoàn thành tốt phần của mình nhé.

Hẹn gặp lại các bạn ở phần 2.


Tạo tài khoản



Đăng nhập


Quên mật khẩu

Hoặc là :