Một số định nghĩa của môn Lý thuyết đồ thị và cả thuật toán tìm đường đi ngắn nhất

tên tài khoản: [You must be registered and logged in to see this link.].
password: Khongb!t

Theo thông báo của khoa lớp chúng ta sẽ thi môn PPNCKH vào ngày 19/11/2011 lúc 17h30 địa điểm chưa xác định. Sẽ tiếp tục cập nhật thông báo mới

Link chi tiết [You must be registered and logged in to see this link.]

Ai có tài liệu lý thuyết đồ thị của thầy share với " love " đi nào ??? 4rum gì chán dữ vậy? Ko có cả 1 bóng ma

các bạn vào đây download về xem nhé.
[You must be registered and logged in to see this link.]
hoặc
[You must be registered and logged in to see this link.]

ĐOÀN TRƯỜNG ĐH LẠC HỒNG
ĐOÀN KHOA CÔNG NGHỆ THÔNG TIN
SỐ:../../../..

ĐOÀN TNCS HỒ CHÍ MINH
Biên Hòa, ngày 20 tháng 02 năm 2011
------------------------

KẾ HOẠCH
Tổ chức Cuộc thi Đố vui tin học năm 2011

Hưởng ứng phong trào Đoàn trong nhà
trường năm 2011. Được sự cho phép của BCH Đoàn trường và Ban lãnh đạo
khoa, BCH …

[ Full reading ]

Trường ĐH Lạc Hồng
Khoa Công Nghệ Thông Tin

Đoàn Trường ĐH Lạc Hồng
Biên Hòa, Ngày 21 Tháng 12 Năm 2010
-------------------------------

KẾ HOẠCH TỔ CHỨC CUỘC THI ICTCUP 2011

1. Giới thiệu về cuộc thi
Trường Đại học Lạc Hồng là một trường
thành viên của Đại học có nhiệm vụ đào tạo nguồn nhân lực công …

[ Full reading ]

Lớp ------ Môn Thi ----- Thứ ---- Ngày Thi --- Giớ Thi --- Phòng Thi

09CT112 ---- TOÁN RỜI RẠC ---- 7 ----- 2/19/2011 --- 09H30 --- B305

09CT112 ----- TOEIC 3-NÓI --- CN ---- 2/20/2011 --- 07H30 ---- G201

CẤU TRÚC DỮ LIỆU
thứ 2.... 14/2/2011 ......... 09H30......... B201

Toán A3
thứ 3...... 15/2/2011 ...... 09H30 D305 & D403

TOEIC 3(nghe,đọc hiểu)
thứ 4 ........ 16/2/2011 ......... 07H30..... PM6-C404

MẠNG MÁY TÍNH
…

[ Full reading ]

xem lich thi ùi thi lại nhe mấy ku.

download [You must be registered and logged in to see this link.]


	Định nghĩa đồ thị vô hướng Đt :G=(V,E) là đt vô hướng trong đó: + V: là tập đỉnh(V≠rỗng) +E: là tập cạnh được tạo thành từ 2 đỉnh ko có thứ tự. Định nghĩa đt có hướng Đt :mG=(V,E) là đt có hướng trong đó: + V: là tập đỉnh(V≠rỗng) +E: là tập cạnh được tạo thành từ 2 đỉnh có thứ tự thuộc V. Định nghĩa Bậc -Đt vô hướng: Cho G=(V,E) là đt vô hướng : + KH: deg(v) + Bậc của 1 đỉnh trong đt vô hướng là số cạnh liền thuộc với đỉnh đó. +Riêng khuyên tại 1 đỉnh được tính 2 lần cho bậc của nó. -Đt có hướng: Cho G=(V,E) là đt có hướng : +Bậc vào của đỉnh V. KH: deg – (v): là tất cả các cạnh có đỉnh cuối là V. +Bậc ra của đỉnh V. KH: deg +(v): là tất cả các cạnh có đỉnh đầu là V. + Khuyên tại 1 đỉnh góp 1 đv vào bậc vào và 1 đv vào bậc ra của đỉnh đó. Định nghĩa đt liên thông : Đt được gọi là đt liên thông nếu có đường đi giữa mọi cặp đỉnh của đt đó. Định nghĩa chu trình: Chu trình là đường đi có đỉnh đầu trùng với đỉnh cuối (u=v). Định nghĩa chu trình sơ cấp: Chu trình đường đi được gọi là đơn nếu chỉ đi qua mỗi cạnh đúng 1 lần. Chu trình Euler: Là chu trình đơn đi qua tất cả các cạnh của đt Đường đi Euler: Một đt có đường đi Euler nếu và chỉ nếu có đúng 2 đỉnh bậc lẽ. Khi đó đường đi sẽ xuất phát từ đỉnh bậc lẻ thứ nhất và kết thức ở đỉnh bậc lẻ thứ 2. Điều kiện có chu trình Euler: Một đt có chu trinh Euler nếu và chỉ nếu có bậc chẵn. Định nghĩa chu trình Hamilton: Chu trình sơ cấp đi qua tất cả các đỉnh của đt được gọi là chu trình Hamilton. Đường đi Hamilton: Đường đi sơ cấp đi qua tất cả các đỉnh của đt được gọi là đường đi Hamilton. Thuật toán tìm đường đi ngắn nhất( Dijkstra) -Thuật toán chỉ dùng cho đt không có cạnh âm -Ý tưởng: +Do không có cạnh âm nên tại mỗi bước sẽ có 1 đỉnh mà tuần tự về nó không thay đổi về sau. +Tại mỗi bước ta cần phải kiểm tra qua tất cả các đỉnh trung gian mà chỉ thực hiện: Chọn 1 đỉnh u có giá trị d[u] nhỏ nhất Chọn u làm đỉnh trung gian để xác định bước kế tiếp -Thuật toán: +Bước 1: Gán V: là tập các đỉnh của đt; S=rỗng chứa đường đi ngắn nhất; L(a)=0 gán giá trị 0 cho đỉnh đầu tiên; L(v) = oo các đỉnh còn lại trong đt gán = oo +Bước 2: Tại đỉnh xuất phát tìm các đỉnh liền kề Tính giá trị khi đi đến đỉnh đó theo chu trình: L(v)=min{L(v);L(a)+W(a,v)}; trong đó: L(a): giá trị của đỉnh xuất phát; W(a,v): giá trị khi đi từ đỉnh xuất phát đến đỉnh kế tiếp. Chọn đỉnh mà đường đi đến đó có giá trị nhỏ nhất cho vào S Tiếp tục tìm các đỉnh kề với đỉnh được chọn. Tính giá trị khi đi đến đỉnh mới L(v)mới=min{Lv)mới; L(v)cũ+ W(v cũ, v mới)}; lấy đỉnh đó cho vào S nếu có giá trị là nhỏ nhất tiếp tục thự hiện cho đến hết. +Bước 3: In ra đường đi ngắn nhất


	thanks nha


	bạn nài biết giải thì tranh thủ giả rõ từng bước rồi poss lên cho mọi ngươi cùng xem nhé. Bài này là ví dụ trên lớp mà mình giải hoài ko ra. http://www.mediafire.com/?g0u6r1bjkkn1r76


	ai có giải được thì coi lại cho với giải rùi mà đường đi ko biết giải thick sao hết a->c->d->e->g->z và tổng bằng 16


	tổng bằng 16 là đúng