ĐẠi học sư phạM ĐÀ NẴng khoa toán lớp cao học phưƠng pháp toán sơ CẤp k25 Đề tài : ĐƯỜng đi hamilton



tải về 220.16 Kb.
trang1/3
Chuyển đổi dữ liệu21.08.2016
Kích220.16 Kb.
#25785
  1   2   3



ĐẠI HỌC SƯ PHẠM ĐÀ NẴNG

KHOA TOÁN

LỚP CAO HỌC PHƯƠNG PHÁP TOÁN SƠ CẤP K25

*****

Đề tài : ĐƯỜNG ĐI HAMILTON

Tiểu luận kết thúc học phần

Môn : Lý thuyết đồ thị
­NHÓM THỰC HIỆN :

Lê Thị Sơn, Nguyễn Hạ Thi Giang, Nguyễn Ngọc Mỹ,

Nguyễn Phương Thảo, Lê Thiện Trung.


Người Hướng Dẫn : PGS.TSKH Trần Quốc Chiến
Đà Nẵng – 2012
MỤC LỤC

Lời giới thiệu………………………………………………………………………2

CHƯƠNG 1 : CÁC KHÁI NIỆM VỀ ĐỒ THỊ.


  1. Đồ thị - Cạnh - Đỉnh………………………………………………………..5

  2. Bậc – Nửa bậc……………………………………………………………....6

  3. Dãy – Đường đi – Chu trình………………………………………………..8

  4. Đồ thị liên thông…………………………………………………………..10

  5. Đồ thị con - Thành phần liên thông……………………………………….10

  6. Đồ thị k-chính quy………………………………………………………...12

CHƯƠNG 2 : ĐƯỜNG ĐI HAMILTON.

  1. Định nghĩa………………………………………………………………...14

  2. Điều kiện cần……………………………………………………………...14

  3. Điều kiện đủ………………………………………………………………16

  • Đồ thị vô hướng………………………………………………..17

  • Đồ thị có hướng………………………………………………..21

  • Một số kết quả cho đồ thị k-liên thông………………………...23

  • Một số kết quả cho đồ thị t- khó……………………………….25

  • Một số kết quả cho đồ thị k – chính quy……………………….27

CHƯƠNG 3 : ỨNG DỤNG VÀ BÀI TẬP.

Lời cảm ơn.

Tài liệu tham khảo.
Giới thiệu

Sự ra đời của Lý thuyết đồ thị bắt nguồn từ những bài toán tưởng chừng rất đơn giản. Từ bài toán 7 cây cầu ở Konigsberg đến đường đi Hamilton là 1 bước phát triển vượt bậc của Toán học trong lĩnh vực này. Cùng với thời gian và sự vươn lên mạnh mẽ của lĩnh vực công nghệ, khoa học kỹ thuật, Lý thuyết đồ thị đã có những đóng góp cực kỳ to lớn về mạng máy tính, mạng lưới giao thông vận tải, lý thuyết tối ưu.

Về mặt thuật toán, có những định lý, bài tập được chứng minh đơn giản nhưng lại có hàm lượng tư duy rất cao. Nhiều bài toán đã ra đời để lại những dấu ấn mạnh mẽ trong nhiều lĩnh vực khoa học như : Đường đi Euler, đường đi Hamilton, Luồng vận tải…

Trong khuôn khổ 1 tiểu luận chúng em chỉ xin được khai thác về bài toán đường đi Hamilton và những phương pháp vận dụng giải bài tập. Đã có nhiều ứng dụng trong mạng tin học ra đời từ thuật toán này nhưng vì lý do hạn hẹp về thời gian và hạn chế số lượng trang nên Tiểu luận này gồm có :



  • Chương 1 : Các khái niệm cơ bản trong LTĐT.

  • Chương 2 : Bài toán đường đi Hamilton và các định lý liên quan.

  • Chương 3 : Ứng dụng giải những bài tập.

Vì những lý do trên mà tiểu luận chỉ hệ thống lại các định lý, khái niệm mà không chứng minh các mệnh đề, hệ quả và ví dụ.
*****

Nhóm thực hiện :




STT

Họ Và Tên

Công Việc

Chữ Ký

Nhận Xét của giáo viên

1

Lê Thị Sơn

Chương 2








2

Nguyễn Hạ Thi Giang

Chương 3








3

Nguyễn Thị Ngọc Mỹ

Chương 2








4

Nguyễn Phương Thảo

Chương 1








5

Lê Thiện Trung

Chương 1









CHƯƠNG 1 : TỔNG QUAN VỀ ĐỒ THỊ

*****

    1. Đồ thị - Cạnh – Đỉnh :

      1. Đồ thị vô hướng : G = (V,E) gồm một tập V các đỉnh và tập E các cạnh. Mỗi cạnh e E được liên kết với một cặp đỉnh v, w ( không kể thứ tự).

v w

      1. Đồ thị có hướng : G = (V,E) gồm một tập V các đỉnh và tập E các cạnh có hướng gọi là cung. Mỗi cạnh e E được liên kết với một cặp đỉnh v, w có thứ tự.

v w

      1. Đồ thị lót : Cho đồ thị có hướng G = (V,E). Nếu ta thay đổi mỗi cung của G bằng một cạnh, thì đồ thị vô hướng nhận được gọi là đồ thị lót của G.

Ghi chú : Đồ thị vô hướng có thể xem là đồ thị có hướng trong đó mỗi cạnh e = (v,w) tương ứng với hai cung (v,w) và (w,v).

      1. Đỉnh – cạnh :

Cho đồ thị (có hướng hoặc vô hướng) G = (V,E).

        • Nếu cạnh e liên kết đỉnh v, w thì ta nói đỉnh e liên thuộc đỉnh v, w, các đỉnh v, w liên thuộc cạnh e, các đỉnh v, w là các đỉnh biên của cạnh e đỉnh v kề với đỉnh w.

        • Cho đồ thị G, A(G) là tập các đỉnh không kề nhau (các đỉnh độc lập nhau). Số phần tử lớn nhất của A(G) được gọi chỉ số độc lập.

Kí hiệu :

        • Nếu chỉ có duy nhất một cạnh e liên thuộc với cặp đỉnh v, w, ta viết e = (v, w). Nếu e là cung thì v gọi là đỉnh đầu và w gọi là đỉnh cuối của cung e.

        • Nếu có nhiều cạnh liên kết với cùng một cặp đỉnh thì ta nói đó là cạnh song song.

        • Cạnh có 2 đỉnh liên kết trùng nhau gọi là khuyên.

        • Đỉnh không kề với đỉnh khác gọi là đỉnh cô lập.

        • Số đỉnh của đồ thị gọi là bậc của đồ thị.

        • Số cạnh hoặc số cung của đồ thị gọi là cỡ của đồ thị.

      1. Các loại đồ thị liên quan :

  • Đồ thị hữu hạn là đồ thị có bậc và cỡ hữu hạn.

  • Đồ thị đơn là đồ thị không có khuyên và không có cạnh song song.

  • Đồ thị vô hướng đủ là đồ thị mà mọi cặp đỉnh đều kề nhau.

  • Đồ thị có hướng đủ là đồ thị có đồ thị lót đủ.




    1. Khái niệm Bậc :

      1. Bậc :

Cho đồ thị G = (V, E)

  • Bậc của đỉnh v V là tổng số cạnh liên thuộc với nó và ký hiệu là d(v).

  • Nếu đỉnh có khuyên thì mỗi khuyên được tính là 2 khi tính bậc, như vậy:

d(v) :=Số cạnh liên thuộc + 2*Số khuyên

Từ định nghĩa suy ra , đỉnh cô lập trong đồ thị đơn là đỉnh có bậc bằng 0.

  • Số bậc lớn nhất của G ký hiệu là .

  • Số bậc nhỏ nhất của G gọi là .

  • Đỉnh treo là đỉnh có bậc bằng 1.

      1. Nửa bậc:

Cho G = (V,E) là đồ thị có hướng, v V.

  • Nửa bậc ra của đỉnh v, kí hiệu là dO(v), là số cung đi ra từ đỉnh v (v là đỉnh đầu).

  • Nửa bậc vào của đỉnh v V, kí hiệu dI(v), là số cung đi tới đỉnh v (v là đỉnh cuối).

Ví dụ về bậc :

Trong đồ thị này, ta có :

d(x1) = 6 , d(x2) = d(x3) = 4, d(x4) = 3 , d(x5) = 0 , d(x6) = 1

Đỉnh x1 có hai khuyên liên thuộc.

Có hai cạnh song song liên thuộc đỉnh x2

và đỉnh x3.

Đỉnh x5 là đỉnh cô lập.

Đỉnh x6 là đỉnh treo.


Ví dụ về nửa bậc :

Xét đồ thị có hướng sau :

Trong đồ thị có hướng này ta có:

dI(x1) = 0 , dO(x1) = 2, dI(x2) = 1 , dO(x2) = 2

dI(x3) = 2 , dO(x3) = 1, dI(x4) = 2 , dO(x4) = 2

dI(x5) = 1 , dO(x5) = 1, dI(x6) = 2 , dO(x6) = 0
Bổ đề bắt tay ( Hand Shaking Lemma) : Cho đồ thị G = (V,E). Khi đó :

i) Tổng bậc các đỉnh của đồ thị là số chẵn và .

ii) Nếu G là đồ thị có hướng thì : , trong đó card(E) là số phần tử của tập E.

Hệ quả 1.1 : Số đỉnh bậc lẻ của đồ thị vô hướng là số chẵn.

Ghi chú : Bổ đề trên có tên bổ đề bắt tay từ bài toán thực tế sau:

Trong một hội thảo, các đại biểu bắt tay nhau. Khi đó tổng số lần bắt tay của tất cả đại biểu bao giờ cũng là số chẵn.


      1. Các loại đồ thị liên quan :

  • Đồ thị đầy đủ : Đồ thị Kn là đồ thị đơn, đủ n đỉnh đều có duy nhất một cạnh liên kết).

Ví dụ: sau đâylà đồ thị K5


Mệnh đề 1.1 : Mọi đỉnh của đồ thị Kn có bậc n-1 và có n(n-1)/2 cạnh.

  • Đồ thị lưỡng phân :

Đồ thị lưỡng phân : G = (V,E) là đồ thị mà tập các đỉnh được phân làm 2 tập rời nhau V1 và V2 sao cho mỗi cạnh của nó liên kết với một đỉnh thuộc V1 và một đỉnh thuộc V2 .

ký hiệu : G = ({V1 ,V2},E).

Đồ thị lưỡng phân đầy đủKm,n : là đồ thị lưỡng phân ({V1 ,V2},E) với tập V1 có m đỉnh và tập V2 có n đỉnh và mỗi đỉnh của V1được nối với mỗi đỉnh của V2 bằng một cạnh duy nhất.

Ví dụ : sau đây là đồ thị K3,3
Mệnh đề 1.2 : Cho đồ thị lưỡng phân đủ Km,n=({V1 ,V2},E) với tập V1 có m đỉnh và tập V2 có n đỉnh. Khi đó mỗi đỉnh trong V1 có bậc là n và mỗi đỉnh trong V2 có bậc là m và Km,nm.n cạnh.


  • Đồ thị chính quy : là đồ thị mà các đỉnh kề nhau có bậc bằng nhau.

Đồ thị k- chính quy : là đồ thị chính quy mà mỗi đỉnh có số bậc bằng k.

Ví dụ :

Đồ thị 0 - chính quy là : Đồ thị gồm các đỉnh cô lập.

Đồ thị 1 - chính quy là : Đồ thị gồm các cạnh không nối với nhau.

Đồ thị 2 – chính quy là : Đồ thị gồm các chu trình không nối với nhau



Đồ thị chính quy mạnh : là đồ thị chính quy mà các đỉnh không kề nhau có bậc bằng nhau.

Ví dụ : là đồ thị k – chính quy mạnh với mọi n.

    1. Dãy - Đường đi - chu trình :

      1. Dãy :

  • Dãy µ từ đỉnh v đền đỉnh w : là dãy các đỉnh và các cạnh nối tiếp nhau bắt đầu từ đỉnh v và kết thúc tại đỉnh w. Số cạnh trên dãy µ gọi là độ dài của dãy µ.

  • Độ dài của Dãy :

Dãy µ từ đỉnh v đến đỉnh w độ dài n được biểu diễn như sau :

µ=(v, e1, v1, e2,v2,….,vn-1,en,w )

trong đó : vi(i=1,…,n-1) là các đỉnh trên dãy và ei(i=1,…,n) là các cạnh trên dãy liên thuộc đỉnh kề trước và sau nó. Các đỉnh và các cạnh trên dãy có thể lắp lại.


  • Dãy có hướng trong đồ thị có hướng là dãy các đỉnh và cung nối tiếp nhau (e1, e2,….,en) thỏa mãn đỉnh cuối cùng của cung ei là đỉnh đầu của cung ei+1, i=1,…n-1.

  • Định lý 1.1 :

(i) Trong đồ thị vô hướng mỗi dãy từ đỉnh v đến w chứa đường đi sơ cấp từ v đến w.

(ii) Trong đó đồ thị có hướng mỗi dãy từ đỉnh v đến w chứa đường đi có hướng sơ cấp từ v đến w.



      1. Vòng :

  • Vòng là dãy có đỉnh đầu và đỉnh cuối trùng nhau

  • Vòng có hướng là dãy có hướng có đỉnh đầu và đỉnh cuối trùng nhau.

      1. Đường đi :

  • Đường đi từ đỉnh v đến đỉnh w là dãy từ đỉnh v đến đỉnh w, trong đó cá cạnh không lặp lại.

  • Đường đi sơ cấp là đường đi không đi qua một đỉnh quá 1 lần.

  • Đường đi có hướng trong đó đồ thị có hướng là dãy có hướng, trong đó các cung không lặp lại.

  • Đường đi có hướng sơ cấp là đường đi có hướng không đi qua một đỉnh quá 1 lần.

      1. Chu trình :

  • Chu trình là đường đi có đỉnh đầu và đỉnh cuối trùng nhau.

  • Chu trình sơ cấp là chu trình không đi qua một đỉnh quá 1 lần.

  • Chu trình có hướng là đường đi có hướng đỉnh đầu và đỉnh cuối trùng nhau.

  • Chu trình có hướng sơ cấp là chu trình có hướng không đi qua một đỉnh qua 1 lần.

  • Định lý 1.2 : Đồ thị G lưỡng phân khi và chỉ khi G không chứa chu trình độ dài lẻ.

      1. Trọng đồ :

  • Trọng đồ (có hướng ) là đồ thị (có hướng ) mà mỗi cạnh (cung) của nó được gán một số .

  • Trọng đồ được biểu diễn bởi G =(V,E,w), trong đó V là tập các đỉnh , E là tập các cạnh (cung) và w: E­­­­­→R là hàm số trên E,w(e) là trọng số của cạnh (cung) e với mọi eE .

Trong trọng đồ độ dài trọng số của đương đi µ là tổng các trọng số trên đường đi đó.


    1. Đồ thị liên thông :

  • Đồ thị vô hướng gọi là liên thông, nếu mọi cặp đỉnh của nó đều có đường đi nối chúng với nhau.

  • Đồ thị có hướng gọi là liên thông mạnh, nếu mọi cặp đỉnh của nó đều có đường đi có hướng nối chúng với nhau.

  • Đồ thị có hướng gọi là liên thông yếu, nếu đồ thị lót (vô hướng) của nó liên thông.

  • Đồ thị có hướng gọi là bán liên thông, nếu với mọi cặp đỉnh (u,v) bao giờ cũng tồn tại đường đi có hướng từ u đến v hoặc từ v đến u.

    1. Đồ thị con – Thành phần liên thông :

      1. Đồ thị con : Cho đồ thị G = ( V, E ). Đồ thị G’ = ( V’, E’ ) gọi là đồ thị con của G nếu V’ V và E’ E

  • Nếu F E, thì ký hiệu G – F là đồ thị con ( V, E-F ) của G gồm tập đỉnh V và tập cạnh ( cung ) E – F

  • Nếu U V, thì ký hiệu G- U là đồ thị con của G thu được từ G sau đó loại bỏ các đỉnh trong U và các cạnh liên thuộc chúng

  • Cho U V, đồ thị con của G sinh bởi U (ký hiệu < U >) là đồ thị ( U, EU) với

EU = { e E / e liên thuộc đỉnh trong U }

  • Đồ thị tự do : là đồ thị không nhận làm đồ thị con.

      1. Thành phần liên thông :

  • Đồ thị con G’ = ( V’, E’ ) của đồ thị ( có hướng ) G (V,E) gọi là thành phần liên thông (mạnh ) của đồ thị G.

  • Nếu nó là đồ thị con liên thông (mạnh) tối đại của G, tức là không tồn tại đồ thị con liên thông (mạnh) G’’= (V”,E”) ≠ G’ của G thỏa V’ V”, E’ E”

Ví dụ : Xét đồ thị G = ( V,E) ở ví dụ trước.


Đồ thị G1 = (V1, E1), với V1 = { x1, x2, x3, x4} và E1= { e1, e2, e3, e4} là đồ thị con của đồ thị G nhưng khong phải thành phần liên thông.

Đồ thị G2 = { V – {x5} , E } = < V – {x5} > là thành phần liên thông của G.

Định lý 1.3 : Cho đồ thị đơn G = (V,E ) với n đỉnh, và k thành phần liên thông. Khi đó số cạnh m của đồ thị thỏa bất đẳng thức

n – k m

Hệ quả 1.2: Mọi đơn đồ thị n đỉnh với số cạnh lớn hơn là liên thông.


    1. Đồ thị k – liên thông :

      1. Đồ thị k – cạnh liên thông :

Cho đồ thị G = (V,E).

  • Tập tách cạnh : Tập cạnh FE gọi là tập hợp tách cạnh của đồ thị liên thông G, nếu G-F không liên thông.

  • Tập cắt cạnh : Hơn nữa, nếu F là tập hợp tách cạnh cực tiểu ( tức không tồn tại F’F, F’ F, F’ là tập tách cạnh ), thì F gọi là tập cắt cạnh. Nếu tập cắt cạnh chỉ có một cạnh,thì cạnh đó gọi là cầu

Đại lượng

= min{card (F) /F là tập tách cạnh của G}

gọi là số liên thông cạnh của G.



  • Đồ thị k – cạnh liên thông : Đồ thị G gọi là k - cạnh liên thông, nếu mọi tập tách cạnh có ít nhất k cạnh.

Ghi chú. Từ định nghĩa ta có

k k, G là k - cạnh liên thông

= max {k / G là k - cạnh liên thông}



      1. Đồ thị k – liên thông :

  • Tập tách đỉnh : Tập đỉnh UV gọi là tập hợp tách đỉnh của đồ thị liên thông G, nếu G- U không có liên thông.

  • Tập cắt đỉnh : Hơn nữa, nếu U là tập hợp tách đỉnh cực tiểu (tức không tồn tại U’U, U’U, U’ là tập hợp tách đỉnh) thì U gọi là tập cắt đỉnh. Nếu tập tách đỉnh chỉ có 1 đỉnh, thì đỉnh đó gọi là đỉnh tách .

Đại lượng k(G ) = min{card (U) /U là tập tách đỉnh của G} gọi là số liên thông đỉnh của G

  • Đồ thị k – liên thông : Đồ thị G gọi là k- liên thông, nếu mọi tập tách đỉnh có ít nhất k đỉnh.

Ghi chú : Từ định nghĩa ta có

    • k(G) k k thì G là k - liên thông và k(G) = max { k / G là k - liên thông}

    • Nếu k(G) = k thì G là k – liên thông chặt.

Ví dụ : Với G là đơn đồ thị bất kì, ta có :

k(G) = 3. Khi đó, (G) là đồ thị 2-liên thông hoặc 3-liên thông hoặc 3-liên thông chặt.

Ghi chú :

(i) Tập V và V – {v}vV đều không phải là tập tách đỉnh

(ii) Đồ thị đủ Kn không có tập tách đỉnh. Vì vậy ta qui ước số liên thông đỉnh của Kn là (n-1).

Ví dụ : Xét đồ thị sau.


f

b

Các tập cạnh sau.

{b,c} , {e,g} , {b,c,d} , {d,e,g} , {d}

Là tập tách cạnh, trong đó cạnh d là cầu, {b,c} và {e,g} là các tập cắt cạnh.

Các tập đỉnh sau

{2,3} , {3,4} , {3} , {4} , {5,7}

Là tập tách đỉnh, trong đó đỉnh {3,4} là đỉnh tách , {5,7} là các tập cắt đỉnh.

  1   2   3




Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2024
được sử dụng cho việc quản lý

    Quê hương