The Internet belongs to everyone. Let’s keep it that way.

Protect Net Neutrality
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

Intuon Jumpawat

on 29 November 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of ทฤษฏีกราฟ

ทฤษฎีกราฟ
กราฟและองค์ประกอบของกราฟ
บทนิยาม : กราฟ (Graph) ประกอบด้วย เซตจำกัดสองเซต คือ เซตที่ไม่เป็นเซตว่างของจุดยอด (Vertex) แทนด้วยสัญลักษณ์
V(G) และ เซตของเส้นเชื่อม (Edge) ที่เชื่อมระหว่างจุดยอด แทนด้วยสัญลักษณ์ E(G)
1. V(G) = {a,b,c,d,e}
2. E(G) = { l1,l2,l3,l4,l5}
3. |V(G)| = 5
4. |E(G)| = 5
A
B
C
D
E
l1
l2
l3
l4
l5
ความรู้เบื้องต้นเกี่ยวกับกราฟ
การประชิด
1. ถ้ามีเส้นเชื่อมระหว่างจุด A และ B
เรียก A และ B ว่า จุดประชิด
2. ใช้สัญลักษณ์ AB แทนเส้นเชื่อมจุด A และ B เรียก A และ B ว่า จุดยอดหรือปลายของเส้น AB
A
b
A
B
ลักษณะของเส้นเชื่อม
1. เส้นเชื่อมขนาน (Parallel edge) คือ เส้นเชื่อมที่มากกว่าเส้นที่เชื่อมจุดยอดคู่เดียวกัน
2. เส้นเชื่อมวงวน (Loop) คือ เส้นเชื่อมที่จุดปลายทั้งสองข้างเป็นจุดเดียวกัน
ชนิดของกราฟ
กราฟเชิงเดียว (Simple graph)

กราฟที่ไม่มีเส้นเชื่อมขนานและไม่มีเส้นเชื่อมวงวน
G1
G2
G3
G4
a
b
c
d
e
f
กราฟหลายเชิง (Multi graph)

กราฟที่มีเส้นเชื่อมขนานและเส้นเชื่อมวงวน
a
b
c
d
a
b
c
d
l1
l2
l3
l4
l5
ดีกรีของจุดในกราฟ
บทนิยาม : จุดยอดมีดีกรี (Degree) เท่ากับ n ก็ต่อเมื่อ จุดยอดนั้นเป็นจุดยอดของเส้น n เส้น สามารถใช้ deg แทนดีกรีได้
v
2
v
1
v
3
v
4
v
5
v
6
ดีกรี
v
1
= 2
V
2
= 3
v
3
= 3
v
7
v
4
= 2
v
5
= 3
v
6
= 1
v
7
= 0
เพิ่มเติม
1.จุดที่มีดีกรีเท่ากับ 0 เรียกว่า จุดเอกเทศ (Isolated vertex)
2.จุดที่มีดีกรี = 1 เรียกว่า จุดปลาย (End vertex)
3.จุดยอดที่มีดีกรีเป็นจำนวนคู่ เรียก “จุดยอดคู่”
4. จุดยอดที่มีดีกรีเป็นจำนวนคี่ เรียก “จุดยอดคี่”
ทฤษฎีบท
1.ผลรวมของดีกรีทุกจุดในกราฟ จะเป็น 2เท่าของเส้นเชื่อม
2.จำนวนจุดยอดคี่ในกราฟต้องเป็นจำนวนคู่
ผลรวมดีกรี = 2L

และผลรวมดีกรีต้องเป็นเลขคู่
a
b
c
d
e
(2)
(3)
(2)
(1)
(4)
เส้นเชื่อม (L) = 6
ผลรวมดีกรี = 2l
= 2x6
= 12
ตัวอย่าง


1. จังหวัดหนึ่งมี 5 อำเภอ ต้องการสร้างถนนโดยให้แต่ละอำเภอ มีถนน
เชื่อมกับอำเภออื่นๆ 3 สาย จะสามารถทำได้หรือไม่
ให้ จุดแทนอำเภอ จะได้จุด 5 จุด
เส้นแทนถนน แต่ละจุดมี 3 เส้น
ผลรวมดีกรี = 5x3
จะได้
= 15
ไม่สามารถทำได้ เพราะ ผลรวมดีกรีไม่ใช่จำนวนคู่
ดังนั้น
กราฟสมสัณฐาน (Isomorphic Graph)
กราฟสมสัณฐาน (Isomorphic Graph)
กราฟที่ถอดแบบกัน คือ ถ้ากราฟนั้นสมสัณฐานกัน
แสดงว่ากราฟทั้งสองมีคุณสมบัติของกราฟที่เหมือนกัน
นั่นคือ มีจุดยอดและเส้นเชื่อมคล้องจองกัน จุดยอดต่อจุดยอด
เส้นเชื่อมต่อเส้นเชื่อม โดยที่การเชื่อมต่อของจุดยอดและเส้นเชื่อม

ที่คล้องจองกันต้องเหมือนกัน
ถ้ากราฟ G และ G สมสัณฐานกัน จะเขียนแทนด้วย G G
1
2
1
2
=
~
1
2
3
4
=
~
1
2
4
3
สับกราฟ
สับกราฟ หรือ กราฟย่อย (Subgraph)
บทนิยาม
กราฟ H จะเป็นสับกราฟของกราฟ G ก็ต่อเมื่อ
1. ทุกจุดยอดของกราฟ H เป็นจุดยอดของกราฟ G
2. เส้นเชื่อมทุกเส้นของ H เป็นเส้นเชื่อมของ G
G
H
1
h
2
h
3
h
4
1
2
3
4
5
2
5
3
4
1
2
3
5
2
3
5
4
กราฟบริบูรณ์ (Complete Graph)
กราฟบริบูรณ์ (Complete Graph)
บทนิยาม
กราฟบริบูรณ์ คือ กราฟที่มีเส้นเชื่อมระหว่างจุดยอดทั้ง 2 จุดเสมอ
k
2
k
3
k
4
k
5
กราฟ K จะมีเส้นเชื่อม n(n-1) เส้น
n
2
การเดินทางในกราฟ
แนวเดิน (Walk)
ในกราฟ G คือ ลำดับสลับของจุดยอดและเส้นเชื่อม
a
b
c
d
A,l1,B,l2,C,l3,D
l1
l2
l3
ข้อสังเกต (แนวเดิน)
1.มีจุดเริ่ม
2. มีจุดสิ้นสุด
3. มีจุดภายใน
v - V ความยาว n
0
n

รอยเดิน (Trail)
แนวเดินในกราฟที่เส้นเชื่อมทั้งหมดแตกต่างกัน
a
b
c
d
e
A,B,C,D,E
A,B,C,B,C
รอยเดิน
ไม่ใช่รอยเดิน
วิถี (Path)
แนวเดินในกราฟที่จุดยอดทั้งหมดแตกต่างกัน
a
b
c
d
A,B,C
A,B,C,D,A
วิถี
ไม่เป็นวิถี
วงจร (Circuit)
แนวเดินที่เส้นเชื่อมทั้งหมดแตกต่างกัน
โดยมีจุดเริ่มต้นและจุดสุดท้ายเป็นจุดยอดเดียวกัน
a
b
d
c
l1
l2
A,l1,B,C,D,A
A,l ,B,C,D
2
วงจร
ไม่เป็นวงจร
วัฏจักร(Cycle)
วงจรที่ไม่มีจุดภายในซ้ำกัน (จุดเริ่มกับจบซ้ำกันได้เท่านั้น)
a
b
c
d
e
A,B,C,E,D,C,A
A,B,C,A
วงจร
วงจร + วัฏจักร
กราฟเชื่อมโยง (Connected Graph)
บทนิยาม
1. u,v เชื่อมโยงเมื่อมีวิถี u-v ได้
2.ถ้ามีวิถีระหว่าง 2 จุดใดๆใน G แล้ว G จะเป็นกราฟเชื่อมโยง
G
1
a
b
c
d
A
B
x
y
C
g
2
ทฤษฎี

ให้ G เป็นกราฟเชิงเดียวที่มียอด n จุด
ถ้าจุดแต่ละจุดของ G มีดีกรีมากกว่าเท่ากับ n-1 แล้ว G จะเป็นกราฟเชื่อมโยง
2
ต้นไม้ ( Tree)
บทนิยาม

ต้นไม้ คือ กราฟเชื่อมโยงที่ไม่มีวัฎจักรปรากฎอยู่
กราฟออยเลอร์ (Eulerian graph)
กราฟออยเลอร์ (Eulerian graph)
วงจร (circuit)
คือ แนวเดินซึ่งเริ่มและจบที่จุดเดียวกัน โดยไม่ใช้เส้นเชื่อมซ้ำกัน
วงจรออยเลอร์ (Eulerian circuit)
คือ วงจรซึ่งผ่านจุดยอดและเส้นเชื่อมทั้งหมดในกราฟ
กราฟออยเลอร์ (Eulerian graph)
คือ กราฟที่หาวงจรออยเลอร์ได้
นั่นคือ
กราฟออยเลอร์คือกราฟที่เราสามารถเดินทางจากจุดหนึ่งแล้วกลับมาจุดเดิมได้
โดยไม่เดินซ้ำเส้นทางเดิม
ถ้าเป็นวงจรปิดจะเป็นกราฟออยเลอร์ได้ก็ต่อเมื่อมีดีกรีเป็นจุดคู่
ปัญหากราฟออยเลอร์
ปัญหาสะพานเคอนิกส์เบิร์ก มีอยู่ว่า ณ เมืองเคอนิกส์เบิร์กมีเกาะกลางแม่น้ำพรีเกล (Pregel)
จำนวน 2 เกาะ และมีสะพานที่เชื่อมระหว่างเกาะและเมืองดังรูป
ชาวเมืองเคอนิกส์เบิร์กพยายามหาวิธีเดินข้ามสะพานให้ครบทุกสะพาน
โดยที่ข้ามสะพานแต่ละสะพานเพียงครั้งเดียวและกลับมาที่จุดยอดเริ่มต้น
เลออนฮาร์ด ออยเลอร์ได้แปลงปัญหานี้ให้อยู่ในรูปกราฟ โดยให้อาณาบริเวณ A, B, C, D
แทนด้วยจุดยอดของกราฟ และสะพานแต่สะพานแทนด้วยเส้นเชื่อมของกราฟ
a
b
c
d
ตัวอย่าง
ตัวอย่าง กราฟต่อไปนี้เป็นกราฟออยเลอร์หรือไม่
a
b
c
d
a
b
c
d
e
โดยทฤษฎีบทของออยเลอร์ จะได้ว่า
(1)
(2)
ข้อ 1 ไม่เป็นกราฟออยเลอร์ เนื่องจากมีจุดยอดคี่ ได้แก่ จุด D (ดีกรี 3) และ จุด E (ดีกรี 1)
ข้อ 2 ไม่เป็นกราฟออยเลอร์ เนื่องจากมีจุดยอดคี่ ได้แก่ จุด B (ดีกรี 3) และ จุด C (ดีกรี 5)
Graph theory
ขอขอบคุณ
หนังสือเรียนคณิตศาสตร์ อ.อรรณพ
ขอขอบคุณ
ทฤษฎีกราฟเบื้องต้น. เข้าถึงได้จาก : http://basicgraphtheory.blogspot.com
ทฤษฎีกราฟ. เข้าถึงได้จาก : www.mwit.ac.th/~noon/style/graph.pdf
ทฤษฎีกราฟ. เข้าถึงได้จาก : http://www.slideshare.net
กราฟเชื่อมโยงและกราฟออยเลอร์. เข้าถึงได้จาก : http://www.scimath.org
รายชื่อสมาชิกกลุ่ม
1. ภัทราภรณ์ หนูประสิทธิ์ ม.5/2 เลขที่ 1
2. เบญญาภา นายนนท์ ม.5/2 เลขที่ 4
3. อนัญพร สินทวีเพิ่มพูน ม.5/2 เลขที่ 13
4. อินทุอร จำปาวัฒน์ ม.5/2 เลขที่ 14
5. อรัชพร สุกิจรัตนาภรณ์ ม.5/2 เลขที่ 25
Full transcript