Ltdt- Bai 02 - Tong Quan Ltdt

  • View
    11

  • Download
    0

Embed Size (px)

DESCRIPTION

L thuyt th

Transcript

  • Bi ging L thuyt th

  • th (graph) l mt cu trc ri rc gm cc nh v cc cnh ni cc nh .

    th c k hiu l G = (V, E), trong :

    V l tp nh (vertex),

    E V V l tp hp cc cnh (edge).

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 2

    1

    2

    3

  • CC LOI TH

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 3

  • HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin

    Tin Giang

    Tr Vinh

    Vnh Long

    ng Thp

    Cn Th

    4

  • Mt n th (simple graph) G = (V, E) gm mt tp khng rng V v mt tp cnh E l cc cnh khng sp th t ca cc nh phn bit.

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 5

    1

    2

    3

  • HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin

    Tin Giang

    Tr Vinh

    Vnh Long

    ng Thp

    Cn Th

    6

  • Mt a th (multigraph) G = (V, E) gm mt tp cc nh V, mt tp cc cnh E v mt hm f t E ti {{u, v} | u, v V, u v}. Cc cnh e1, e2 c gi l cnh song song (parallel) (hay cnh bi (multiple)) nu f(e1) = f(e2).

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 7

  • HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin

    Tin Giang

    Tr Vinh

    Vnh Long

    ng Thp

    Cn Th

    8

  • Mt gi th (pseudo graph) G = (V, E) gm mt tp nh V, mt tp cc cnh E v mt hm f t E ti {{u, v} | u, v V}.

    Mt cnh l khuyn (loop) nu f(e) = {u, u} = {u} vi mt nh u no .

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin

    9

  • HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin

    Tin Giang

    Tr Vinh

    Vnh Long

    ng Thp

    Cn Th

    10

  • Mt th c hng (directed graph hoc digraph) G = (V, E) gm tp cc nh V v tp cc cnh E l cc cp c th t ca cc phn t thuc V. Cc cnh y cn c gi l cung (arc).

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 11

  • HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin

    Tin Giang

    Tr Vinh

    Vnh Long

    ng Thp

    Cn Th

    12

  • Mt a th c hng (directed multigraph) G = (V, E) gm mt tp cc nh V, tp cc cnh E v mt hm f t E ti {(u, v) | u, v V}.

    Cc cnh e1 v e2 l cc cnh bi nu f(e1) = f(e2).

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 13

  • Loi Cnh C cnh bi? C khuyn?

    n th V hng Khng Khng

    a th V hng C Khng

    Gi th V hng C C

    th c hng C hng Khng C

    a th c hng C hng C C

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 14

  • CC M HNH TH

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 16

  • HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin

    A

    B

    C

    D

    AB AC AD

    BC BD

    A

    B

    C

    D

    A

    B

    C

    D

    DB DC

    AB AC AD

    BC BD

    DB DC

    18

  • HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin

    A

    B

    C

    D

    AB BA

    AD

    BC

    BD

    A

    B

    C

    D

    A

    B

    C

    D

    CB

    CD

    A

    B

    C

    D

    AC

    CA

    DB

    DC

    DA

    19

  • HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin

    Tin

    Nam

    Minh Vn

    Th

    c

    th quen bit trn tri t c hn 6 t nh v c th hn t t cnh!

    20

  • HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin

    Linda

    Brian

    Raffa Andy

    John

    Steve

    21

  • nh: tc gi

    Cnh: 2 ngi vit chung mt bi bo

    th cng tc (2001) c hn 337000 nh v 496200 cnh.

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 22

  • HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin

    1 2

    3

    4 5

    6

    23

  • 1. A = 0

    2. B = 1

    3. C = A + 1

    4. D = B + A

    5. E = D + 1

    6. E = C + D

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin

    S1 S2

    S3 S4

    S5 S6

    24

  • 1. Xc nh loi th ca cc th sau:

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin

    a

    b

    c

    d

    25

  • 2. Xy dng th nh hng cho cc thnh vin lnh o ca mt cng ty nu:

    Ch tch c nh hng ln gim c nghin cu & pht trin, gim c marketing, gim c iu hnh;

    Gim c nghin cu & pht trin c nh hng ln gim c iu hnh;

    Gim c Marketing nh hng ln Gim c iu hnh;

    Khng ai c th nh hng ln trng phng ti chnh v Trng phng ti chnh khng nh hng ln bt c ai.

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 26

  • 3. Hy xy dng th u tin cho chng trnh sau:

    1. x = 0;

    2. x = x + 1;

    3. y = 2;

    4. z = y;

    5. x = x + 2;

    6. y = x + z;

    7. z = 4;

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 27

  • CNH K, NH K, BC

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 28

  • Hai nh u v v trong mt th v hng G c gi l k hay lin k (adjacent) (hay lng ging (neibor)) nu {u, v} l mt cnh ca G.

    Nu e = {u, v} th e c gi l cnh lin thuc (incident) vi cc nh u v v. Cnh e cng c gi l cnh ni (connect) cc nh u v v.

    Cc nh u v v gi l cc im u mt (endpoint) ca cnh {u, v}.

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 29

  • Bc (degree) ca mt nh trn th v hng l s cc cnh lin thuc vi n, ring khuyn ti mt nh c tnh hai ln cho bc ca n. Ngi ta k hiu bc ca nh v l deg(v).

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin

    30

  • HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin

    Tin Giang

    Tr Vinh

    Vnh Long

    ng Thp

    Cn Th

    3

    6

    5

    3

    5

    31

  • Cho G = (V, E) l mt th v hng c e cnh. Khi :

    C bao nhiu cnh trong th c 10 nh, mi nh c bc bng 7?

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin

    Vv

    ve )deg(2

    32

  • nh l: Mt th v hng c s lng nh bc l l mt s chn.

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 33

  • Khi (u, v) l cnh ca th c hng G, th u c gi l ni ti v v v c gi l ni t u. nh u c gi l nh u (initial vertex), nh v gi l nh cui (terminal hoc end vertex) ca cnh (u, v).

    Cnh e = (u, v) c gi l i t nh u ti nh v hoc i ra nh u vo nh v.

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 34

  • Trong th c hng, bc vo (in-degree) ca nh v, k hiu l deg-(v) l s cc cnh c nh cui l v.

    Bc ra (out-degree) ca nh v, k hiu l deg+(v) l s cc cnh c nh u l v. (Mt khuyn s gp thm 1 n v vo bc vo v 1 n v vo bc ra ca nh cha khuyn)

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 35

  • HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin

    Tin Giang

    Tr Vinh

    Vnh Long

    ng Thp

    Cn Th

    d- = 2, d+ = 1

    d- = 4, d+ = 1

    d- = 2, d+ = 3

    d- = 2, d+ = 4

    d- = 1, d+ = 2

    36

  • Cho G = (V, E) l mt th c hng. Khi :

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin

    VvVv

    Evv )(deg)(deg

    37

  • nh treo (pendant vertex) l nh c bc bng 1.

    nh c lp (isolated vertex) l nh c bc bng 0.

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 38

  • HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin

    Tin Giang

    Tr Vinh

    Vnh Long

    ng Thp

    Cn Th

    Ph Quc

    39

  • MT S N TH C BIT

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 40

  • th y (complete graph) n nh, k hiu l Kn, l mt n th cha ng mt cnh ni mi cp nh phn bit.

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 41

  • th chnh quy (regular graph) l n th m bc ca mi nh u bng nhau.

    Nu bc ca cc nh l n, th th ny c gi l n chnh quy (n regular).

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 42

  • HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin

    2 chnh quy

    3 chnh quy

    4 chnh quy

    43

  • th vng (cycle) Cn, n 3 l mt th c n nh v1, v2 vn v cc cnh {v1, v2}, {v2, v3}, {vn-1, vn} v {vn, v1}.

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 44

  • Mt n th G c gi l th phn i (bipartite graph) nu tp cc nh V c th phn lm hai tp con khng rng, ri nhau V1 v V2 sao cho mi cnh ca th ni mt nh ca V1 vi mt nh ca V2.

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 45

  • HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 46

  • th C6 v K3 c phi l cc th phn i? Gii thch.

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin

    1 2

    3

    4 5

    6

    1

    2

    3

    47

  • th phn i y (complete bipartite graph) Km,n l th c tp nh c phn thnh hai tp con tng ng c m nh v n nh v c mt cnh gia 2 nh nu v ch nu mt nh thuc tp con ny v nh th hai thuc tp con kia.

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 48

  • HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 49

  • TH CON

    TH B PHN

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 50

  • th con (subgraph) ca th G = (V, E) l th H = (W, F) trong W V v F E.

    th H l con ca th G c gi l th b phn (spanning subgraph) ca G khi W = V.

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 51

  • HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin

    1 2

    3

    4 5

    6

    1

    3

    4 5

    6

    1 2

    3

    4 5

    6

    52

  • Th no l 2 nh k nhau?

    Bc ca nh l g?

    Mi lin quan gia s cnh v bc?

    S lng nh bc l ca mt th?

    nh treo? nh c lp?

    th y ?

    th vng?

    th phn i?

    th phn i y ?

    th con? th b phn

    HCMUS 2010 Bi ging L thuyt th ng Nguyn c Tin 53

  • 1. Cho G l mt th n, v hng c s nh