การสร้างกราฟใหม่จากกราฟตัวเก่า
................บางครั้งเราต้องการเพียงบางส่วนของกราฟเพื่อใช้ในการแก้ปัญหา
เช่น เราต้องการเพียงบางส่วนของ ศูนย์คอมพิวเตอร์ขนาดใหญ่ใน New York, Denver,
Detroit, และ Atlanta. เราสามารถเพิกเฉยกับคอมพิวเตอร์ ในศูนย์คอมพิวเตอร์ที่อื่น
ๆ และสายโทรศัพท์ทั้งหมดที่ไม่เชื่อมกับศูนย์คอมพิวเตอร์ทั้ง 4 แห่ง ในกราฟสำหรับ
ระบบขนาดใหญ่ เราสามารถกำจัดสิ่งที่เหมือนกันที่เราสนใจของศูนย์คอมพิวเตอร์ทั้ง
4 แห่งที่เหมือนกันได้และ เราสามารถกำจัดเส้นทางทั้งหมดได้เมื่อเส้นถูกจำกัดออกจากกราฟ
กราฟที่ได้ออกมาจะเรียกว่า subgraph ที่ได้ จากกราฟเดิม
รูป 14 Subgraph of K 3
นิยามที่ 6 subgraph
ของ กราฟ G = ( V,E ) เป็น กราฟ H = ( W, F ) ซึ่ง W ? V และ F ? E
ตัวอย่างที่ 14 กราฟ
G แสดงในรูป 14 เป็น subgraph ของ K 5
วิธีทำ :
มีการรวมเส้นทาง 2 เส้นทางหรือมากกว่านั้น
กราฟใหม่จะเก็บเส้นทางทั้งหมด เรียกว่า union ของกราฟ. เราจะให้นิยามสำหรับพื้นฐาน
union ของกราฟทั้ง 2 กราฟ
นิยามที่ 7 union ของ G
1 = ( v 1 , E 1 ) และ G 2 =
( V 2 , E 2 ) เป็นกราฟที่ประกอบด้วยเซ็ทของจุดยอดของ
V 1 U V 2 และเส้นของ E 1 U E 2 .จะใช้สัญลักษณ์
Union ของ G 1 และ G2 โดย G 1 U G 2
ตัวอย่างที่ 15 หา union
ของ กราฟ G 1 และ G 2 ในรูป 15 (a)
วิธีทำ :
หาเซ็ทของ union G 1
U G 2 ซึ่งจะมี { a,b,c,d,e,f } เป็นจุดยอด. เซ็ทของเส้นเชื่อมของ
union ของเส้นจะเป็นตามรูป 15 (b)
รูปที่ 15 (a) กราฟ G 1 และ
G 2 และ (b) Union ของ G 1 U G 2
|
Home
| Introduction
| Simple
Graph | Bipartite
Graph |
Applications
Graph |
Subgraph |
Exercises
| Links
|