Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

ทฤษฎีกราฟเบื้องต้น

No description
by

Cin atitaya

on 1 December 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of ทฤษฎีกราฟเบื้องต้น

นิยามของกราฟ
บทนิยาม
เราเรียกกราฟที่ไม่มีเส้นเชื่อมขนาน
ทฤษฎีกราฟเบื้องต้น
1. เซตที่ไม่เป็นเซตว่างของจุดยอด (Vertex)


2. เซตของเส้นเชื่อม (Edge) ที่เชื่อมระหว่าง
กราฟ G ประกอบด้วย เซตจำกัด 2 เซต คือ
V(G)

E(G)
ข้อสังเกต
V(G)

ไม่เท่ากับ
เซตว่าง
แต่
E(G)

อาจเป็น
เซตว่างได้
ตัวอย่างที่ 1
กำหนดกราฟ G ดังรูป
จากกราฟ G ที่กำหนดให้ จะได้ว่า
= { , , , , }
= {A, B, C, D}

V(G)

E(G)
แทนด้วยสัญลักษณ์
แทนด้วยสัญลักษณ์
จุดยอด
จุดยอด u และจุดยอด v ของกราฟ
บทนิยาม
เราเรียกจุดยอด u และ v ว่า จุดปลาย (End
เป็นจุดยอดประชิด (Adjacent Vertices)
ก็ต่อเมื่อ มีเส้นเชื่อมระหว่างจุดทั้งสอง
Point) ของเส้นเชื่อมนั้น
ตัวอย่างที่ 2
จากกราฟของตัวอย่างที่ 1 จะเห็นว่า
A
B
C
D
e
1
e
e
e
2
3
4
จุดยอด A และ จุดยอด B เป็นจุดยอดประชิด
จุดยอด B และ จุดยอด C เป็นจุดยอดประชิด
แต่
จุดยอด b และจุดยอด D ไม่เป็นจุดยอดประชิด
จุดยอด c และจุดยอด D ไม่เป็นจุดยอดประชิด
บทนิยาม
เส้นเชื่อมที่เชื่อมจุดยอดเพียงจุดเดียว
จุดยอดคู่เดียวกัน เรียกว่า เส้นเชื่อมขนาน
(Parallel Edges)
เส้นที่เชื่อมตั้งแต่ 2 เส้น ที่เชื่อมระหว่าง
เรียกว่า วงวน (Loop)
ตัวอย่างที่ 3
จากรูปข้างต้นจะเห็นว่า
และ เป็นเส้นเชื่อมขนาน
เส้นเชื่อม เป็นวงวน
e
e
e
1
2
5
Graph)
และไม่มีวงวน ว่า กราฟเชิงเดียว (Simple
ตัวอย่างที่ 4
พิจารณากราฟ
ส่วน กราฟที่มีวงวน หรือมีเส้นเชื่อม ขนาน คือ กราฟหลายเชิง (multigraph)
กราฟ เป็น
กราฟเชิงเดียว





เพราะ ไม่มีทั้งวงวน และเส้นเชื่อมขนาน
เพราะ มีวงวน
กราฟ เป็น
กราฟหลายเชิง
G
G
1
2
2. กราฟเดียวกัน
บทนิยามกราฟเดียวกัน
เรากล่าวว่า กราฟ
G
และกราฟ
H
เป็นกราฟเดียวกัน(Identical) ก็ต่อเมื่อ

V(G)
=
V(H)

และ
E(G)
=
E(H)
ตัวอย่างที่ 1
พิจารณากราฟ G และกราฟ H ดังรูป
จะเห็นว่า
V(G)
= {A, B, C, D} =
V(H)
E(G)
= {AC, BC, BD} =
E(H)
ดังนั้น เราจะกล่าวว่า กราฟ
G
และกราฟ
H
เป็น
กราฟเดียวกัน
3. ดีกรีของจุดสูงสุด
บทนิยามดีกรี
ดีกรี (Degree) คือ จำนวนครั้ง
ทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด v

ใช้สัญลักษณ์
deg v

ที่เส้นเชื่อมเกิดกับจุดยอดว่า ดีกรี
ต่อไปจะเรียกจำนวนครั้งทั้งหมด
แทนดีกรีของ จุดยอด
v
ตัวอย่างที่ 1
กำหนดกราฟ ดังรูป
a
c
d
b
จากรูปจะได้ว่า

deg b = 3
deg c = 4
deg d = 3
ทฤษฎีบท 1
ผลรวมของดีกรีของจุดยอดทุกจุด
ในกราฟเท่ากับสองเท่าของจำนวนเส้น
เชื่อมในกราฟ
ข้อสังเกต
ผลรวมของดีกรีของจุดยอด ทุกจุดในกราฟเป็นจำนวนคู่เสมอ
ตัวอย่างที่ 2
กำหนดกราฟมีดีกรีของจุดยอดต่างๆ
1. 1,2,2,3,3,3
วิธีทำ
ผลรวมดีกรี = 14
จน.เส้นเชื่อม = 7
2. 5,3,3,4,4,4
วิธีทำ
ผลรวมดีกรี = 23
เป็นไปไม่ได้
บทนิยาม
จุดยอดที่มีดีกรีเป็นจำนวนคู่ เรียกว่า จุดยอดคู่ (Even Vertex)
จุดยอดที่มีดีกรีเป็นจำนวนคี่ เรียกว่า จุดยอดคี่ (Odd Vertex)
ตัวอย่างที่ 3
กำหนดกราฟ ดังรูป

a
b
c
d
e
deg a = 2
deg b = 3
deg c = 0
deg d = 3
deg e = 2
a, c ,e
b d
จากรูปจะได้ว่า
ดังนั้น จุดยอด เป็นจุดยอดคู่
จุดยอด
เป็นจุดยอดคี่
ทฤษฎีบท 2
ทุกกราฟจะมีจุดยอด คี่เป็นจำนวนคู่
พิจารณากราฟแยกเป็น 2 กรณี
กรณีที่ 1
เมื่อกราฟไม่มีจุดยอดเป็นคี่
a
b
c
จากกราฟจะได้ว่า
deg a = 2
deg b = 2
deg c = 2
กราฟนี้ไม่มีจุดยอดคี่ หรือมีจุดยอดคี่เป็นศูนย์
นั้นคือ ถ้าจุดยอดทุกจุดเป็นจุดยอดคู่ แสดงว่า
กรณีที่ 2
เมื่อกราฟมีจุดยอดเป็นคี่
a
b
c
d
จากกราฟจะได้ว่า
deg a = 2
deg b = 2
deg c = 3
deg d = 1
กราฟนี้มีจุดยอดคี่ 2 จุด ได้แก่ จุดยอด c กับ จุดยอด d
ดังนั้น กราฟนี้มีจุดยอดคี่เป็นจำนวนคู่
4. แนวเดินและกราฟเชื่อมโยง
1. กราฟ
นิยามแนวเดิน
แนวเดิน หรือ ( )
จุดที่อยู่หน้าและหลังของเส้นนั้น
จุด แต่ละเส้นในลำดับจะอยู่ติดกับ
โดยเริ่มต้นด้วยจุดและสิ้นสุดด้วย
คือ ลำดับของ จุดและ เส้นสลับกัน
u-v walk
u-v
ตัวอย่างที่ 1
พิจารณารูป
a
b
c
d
e
e
e
e
e
1
2
3
4
a , e , b , e , c , e , d , e , e
1
2
3
4
เป็นแนวเดิน
a-e
เส้นแนวเดิน
a-e
อาจเขียนเป็น
a , ab , b , bc , c , cd , d , de , e
ก็ได้
ถ้าจุดยอด และ เป็นจุดยอดเดียวกัน เรียกแนวเดิน ว่า
แนวเดินปิด
ถ้าจุดยอด และ เป็นจุดยอดต่างกัน เรียกแนวเดิน ว่า
แนวเดินเปิด
u-v
u-v
u
v
v
u
นิยามรอยเดิน
รอยเดิน หรือ ( )
แตกต่างกัน
คือ แนวเดิน ที่เส้นทั้งหมด
u-v
u-v trail
u-v
ตัวอย่างที่ 2
พิจารณากราฟ
a
b
c
d
e
e
e
e
e
1
2
3
4
5
แนวเดิน

เป็นรอยเดิน เนื่องจากประกอบด้วยเส้น
a , b , c , a
e ,
1
e
2
และ ซึ่งเป็น
เส้นไม่ซ้ำกัน
e
5
แนวเดิน

a , b , c , d , b , c
ไม่เป็นรอยเดิน เนื่องจากประกอบด้วยเส้น
e , e , e , e , e
1
2
2
3
4
ซึ่งมีเส้น
e
2
เป็น
เส้นที่ซ้ำกัน
รอยเดิน
มี
จุดซ้ำ
กันได้ แต่
เส้น
ต้อง
ไม่ซ้ำ
กัน
นิยามวิถี
วิถี หรือ ( ) คือ
u-v
u-v path
แนวเดิน ที่จุดทั้งหมดต่างกัน
u-v
ตัวอย่างที่ 3
พิจารณากราฟ
a
b
c
d
e
e
e
e
e
1
2
3
4
5
แนวเดิน
เป็นวิถี
เพราะจุดทั้งหมดแตกต่างกัน
a , b , c , d
แนวเดิน
a , b , c , d , b , c
ไม่เป็นวิถี
เพราะ มีจุด
b
และ
c
ซ้ำกัน
นิยามวงจร
วงจร (curcuit ) คือ
รอยเดินที่จุดเริ่มต้นและจุดสุด
ท้ายเป็นจุดเดียวกัน
นิยามวัฏจักร
วัฏจักร ( cycle ) คือ
วงจรที่ไม่มีจุดซ้ำกัน ยกเว้น
จุดเริ่มต้นและจุดสุดท้าย
บทนิยามกราฟเชื่อมโยง
กราฟที่จุดแต่ละสองจุด และ
u v
ที่ต่างกันมีแนวเดิน เสมอ เรียกว่า
u-v
กราฟเชื่อมโยง ( connected graph )
นั่นคือ ถ้าจุดยอดของกราฟ g เพียงคู่เดียว
ไม่มีแนวเดิน กราฟนั้นจะไม่เป็นกราฟ
เชื่อมโยง
พิจารณากราฟ
g :
g :
1
2
a
b
กราฟนี้เป็นกราฟเชื่อมโยง
กราฟนี้เป็นกราฟไม่เชื่อมโยง
เนื่องจากไม่มีวิถีเชื่อมระหว่าง
และ
a
b
5. กราฟออยเลอร

จุดกำเนิด
เกิดจาก ปัญหาสะพานเคอนิกส์เบิร์ก
ดังรูปต่อไปนี้
มีสะพานที่เชื่อมระหว่างเกาะและเมือง
แม่น้ำพรีเกล (Pregel) จำนวน 2 เกาะและ
มีอยู่ว่า ณ เมืองเคอนิกส์เบิร์กมีเกาะกลาง
ชาวเมืองเคอนิกส์เบิร์กพยายามหา
แต่ละสะพานแทนด้วยเส้นเชื่อมของกราฟ
C, D แทนด้วยจุดยอดของกราฟ และสะพาน
ให้อยู่ในรูปกราฟ โดยให้อาณาบริเวณ A, B,
เลออนฮาร์ด ออยเลอร์ได้แปลงปัญหานี้
กลับมาที่จุดยอดเริ่มต้น
ข้ามสะพานแต่ละสะพานเพียงครั้งเดียวและ
วิธีเดินข้ามสะพานให้ครบทุกสะพาน โดยที่
นิยามวงจรออยเลอร์
วงจรออยเลอร์ (Euler trail) คือ
เชื่อมทุกเส้นของกราฟ
รอยเดินซึ่งผ่านจุดยอดทุกจุดและเส้น
ทฤษฎีบท
ให้ G เป็นกราฟเชื่อมโยง จะได้ว่า G

(Eulerian graph)
ออยเลอร์ เรียกว่า กราฟออยเลอร์
ของ G มีดีกรีเป็นจำนวนคู่ กราฟที่มีวงจร
เป็นกราฟออยเลอร์ ก็ต่อเมื่อจุดยอดทุกจุด
ตัวอย่าง
กราฟต่อไปนี้เป็นกราฟออยเลอร์
เพราะ
จุดยอดทุกจุด มีดีกรีเป็นจำนวนคู

บทนิยามรอยเดินออยเลอร์
รอยเดินออยเลอร์(Euler circuit) คือ
วงจรที่ผ่านจุดยอดทุกจุดและเส้นเชื่อมทุกเส้น
ของกราฟ
ทฤษฎีบท
ให้ G เป็นกราฟเชื่อมโยง จะได้ว่า G เป็นกราฟ
ต้นและจุดปลายของรอยเดินออยเลอร์
ยอดที่เป็นจำนวนคี่เหล่านั้นจะเป็นจุดเริ่ม
ดีกรีเป็นจำนวนคี่ไม่เกิน 2 จุด ยิ่งไปกว่านั้น จุด
ที่มีรอยเดินออยเลอร์ ก็ต่อเมื่อ G มีจุดยอดที่เป็น
6. ต้นไม้
บทนิยามต้นไม้
ต้นไม้ (tree) คือ กราฟเชื่อมโยง
ที่ไม่มีรูปปิด (วัฏจักร)
ตัวอย่างที่ 1
พิจารณากราฟต่อไปนี้
จะเห็นว่า กราฟในรูป
(A)
และ
(B)
เป็น
ต้นไม้

กราฟในรูป
(C)

ไม่เป็นต้นไม้
เพราะมีวัฏจักรปรากฏอยู่
กราฟในรูป
(D)

ไม่เป็นต้นไม้
เพราะไม่ใช่กราฟเชื่อมโยง
นิยามต้นไม้แผ่ทั่ว
ต้นไม้แผ่ทั่ว (spanning tree) คือ
ต้นไม้ที่ใช้จุดยอดของกราฟครบทุกจุด
ตัวอย่าง
พิจารณากราฟต่อไปนี้
เราสามารถหาต้นไม้แผ่ทั่วจากกราฟ
นี้ได้ทั้งหมด
สาม
แบบ
ข้อสังเกต
ต้นไม้เป็นกราฟเชิงเดียว ถ้ากราฟมีวงวน หรือ
มีเส้นเชื่อมขนาน กราฟนั้นจะไม่เป็นต้นไม้
ต้นไม้แผ่ทั่วที่มีจุดยอด n จุด จะมีเส้นเชื่อม n - 1 เส้น
ต้นไม้ที่แผ่ทั่วน้อยที่สุด
คือ ต้นไม้แผ่ทั่วที่มีผลรวมค่าน้ำหนัก
ของแต่ละเส้นเชื่อมน้อยที่สุด
จาก
ตัวอย่าง
ที่แล้ว จะเห็นได้ว่า ต้นไม้แผ่ทั่วที่น้อย
ที่สุด คือ
ซึ่งมีผลรวมค่าน้ำหนัก เท่ากับ 3 + 4 + 1 = 8
วิธีการหาต้นไม้แผ่ทั่วน้อยที่สุด

ทำให้เกิดวัฏจักร
โดยเริ่มจากเส้นที่มีค่าน้ำหนักน้อยที่สุด และไม่เลือกเส้นที่
ทำได้โดยการเลือกเส้นเชื่อมจากกราฟที่กำหนดให้ทีละเส้น
e
e
e
e
e
1
2
3
4
5
ในแต่ละข้อ จงหาจำนวนเส้นเชื่อมของกราฟ
สมาชิกกลุ่ม 3
ศิรินทร์ มณีจันทร์ เลขที่
25
มธุรส กาญจนอารีรัตน์ เลขที่
35
อทิตยา พีรพรวิมล เลขที่
42
วิชญ์ชฎา ลักษมัญ เลขที่
43
อรปรียา ลิมป์วรกุล เลขที่
44
deg a = 2
Full transcript