ทฤษฎีเครือข่าย - เครือข่ายโทโพโลยี

โทโพโลยีเครือข่ายเป็นการแสดงภาพกราฟิกของวงจรไฟฟ้า มีประโยชน์ในการวิเคราะห์วงจรไฟฟ้าที่ซับซ้อนโดยการแปลงเป็นกราฟเครือข่าย โทโพโลยีเครือข่ายเรียกอีกอย่างว่าGraph theory.

คำศัพท์พื้นฐานของเครือข่ายโทโพโลยี

ตอนนี้ให้เราพูดคุยเกี่ยวกับคำศัพท์พื้นฐานที่เกี่ยวข้องกับโครงสร้างเครือข่ายนี้

กราฟ

กราฟเครือข่ายเรียกง่ายๆว่า graph. ประกอบด้วยชุดของโหนดที่เชื่อมต่อกันด้วยสาขา ในกราฟโหนดเป็นจุดร่วมของสองสาขาหรือมากกว่า บางครั้งเพียงสาขาเดียวอาจเชื่อมต่อกับโหนด สาขาคือส่วนของเส้นตรงที่เชื่อมต่อสองโหนด

วงจรไฟฟ้าหรือเครือข่ายใด ๆ สามารถแปลงให้เทียบเท่าได้ graphโดยการแทนที่องค์ประกอบแบบพาสซีฟและแหล่งจ่ายแรงดันด้วยวงจรลัดและแหล่งกำเนิดกระแสด้วยวงจรเปิด นั่นหมายความว่าส่วนของเส้นในกราฟแสดงถึงกิ่งก้านที่เกี่ยวข้องกับองค์ประกอบแฝงหรือแหล่งกำเนิดแรงดันไฟฟ้าของวงจรไฟฟ้า

ตัวอย่าง

ให้เราพิจารณาสิ่งต่อไปนี้ electric circuit.

ในวงจรข้างต้นมี four principal nodes และมีป้ายกำกับ 1, 2, 3 และ 4 มี seven branches ในวงจรข้างต้นซึ่งสาขาหนึ่งมีแหล่งกำเนิดแรงดันไฟฟ้า 20 V อีกสาขาหนึ่งมีแหล่งจ่ายกระแส 4 A และอีกห้าสาขาที่เหลือมีตัวต้านทานที่มีความต้านทาน 30 Ω, 5 Ω, 10 Ω, 10 Ωและ 20 Ωตามลำดับ

เทียบเท่า graph ที่สอดคล้องกับวงจรไฟฟ้าด้านบนแสดงในรูปต่อไปนี้

ในกราฟด้านบนมี four nodesและมีป้ายกำกับ 1, 2, 3 และ 4 ตามลำดับ สิ่งเหล่านี้เหมือนกับโหนดหลักในวงจรไฟฟ้า มีsix branches ในกราฟด้านบนและมีป้ายกำกับ a, b, c, d, e & f ตามลำดับ

ในกรณีนี้เราได้ one branch less ในกราฟเนื่องจากแหล่งจ่ายกระแส 4 A ถูกสร้างเป็นวงจรเปิดในขณะที่แปลงวงจรไฟฟ้าเป็นกราฟที่เท่ากัน

จากตัวอย่างนี้เราสามารถสรุปประเด็นต่อไปนี้ -

number of nodes ที่มีอยู่ในกราฟจะเท่ากับจำนวนโหนดหลักที่มีอยู่ในวงจรไฟฟ้า
number of branches ที่มีอยู่ในกราฟจะน้อยกว่าหรือเท่ากับจำนวนสาขาที่มีอยู่ในวงจรไฟฟ้า

ประเภทของกราฟ

ประเภทของกราฟต่อไปนี้ -

กราฟที่เชื่อมต่อ
กราฟที่ไม่เชื่อมต่อ
กราฟกำกับ
กราฟที่ไม่ได้บอกทิศทาง

ตอนนี้ให้เราพูดคุยเกี่ยวกับกราฟเหล่านี้ทีละรายการ

กราฟที่เชื่อมต่อ

หากมีอย่างน้อยหนึ่งสาขาระหว่างโหนดใด ๆ ในสองโหนดของกราฟจะเรียกว่าเป็น connected graph. นั่นหมายความว่าแต่ละโหนดในกราฟที่เชื่อมต่อจะมีหนึ่งสาขาหรือมากกว่าที่เชื่อมต่อกับมัน ดังนั้นจะไม่มีโหนดใดที่ถูกแยกออกหรือแยกออกจากกัน

กราฟที่แสดงในตัวอย่างก่อนหน้าคือ a connected graph. ที่นี่โหนดทั้งหมดเชื่อมต่อกันด้วยสามสาขา

กราฟที่ไม่เชื่อมต่อ

หากมีโหนดอย่างน้อยหนึ่งโหนดในกราฟที่ยังคงไม่ได้เชื่อมต่อกันแม้แต่สาขาเดียวก็จะเรียกว่าเป็นไฟล์ unconnected graph. ดังนั้นจะมีโหนดแยกอย่างน้อยหนึ่งโหนดในกราฟที่ไม่เชื่อมต่อ

พิจารณากราฟที่แสดงในรูปต่อไปนี้

ในกราฟนี้โหนด 2, 3 และ 4 เชื่อมต่อกันด้วยสองสาขา แต่ไม่มีแม้แต่สาขาเดียวที่เชื่อมต่อกับnode 1. ดังนั้นโหนด 1 จึงกลายเป็นisolated node. ดังนั้นกราฟด้านบนจึงเป็นไฟล์unconnected graph.

กราฟกำกับ

หากกิ่งก้านทั้งหมดของกราฟแสดงด้วยลูกศรกราฟนั้นจะถูกเรียกว่า a directed graph. ลูกศรเหล่านี้ระบุทิศทางการไหลของกระแสในแต่ละสาขา ดังนั้นกราฟนี้จึงเรียกอีกอย่างว่าoriented graph.

พิจารณากราฟที่แสดงในรูปต่อไปนี้

ในกราฟด้านบนทิศทางของการไหลของกระแสจะแสดงด้วยลูกศรในแต่ละสาขา ดังนั้นจึงเป็นdirected graph.

กราฟที่ไม่ได้บอกทิศทาง

หากกิ่งก้านของกราฟไม่ได้แสดงด้วยลูกศรกราฟนั้นจะถูกเรียกว่าเป็นไฟล์ undirected graph. เนื่องจากไม่มีทิศทางของการไหลของกระแสดังนั้นจึงเรียกกราฟนี้ว่าเป็นunoriented graph.

กราฟที่แสดงในตัวอย่างแรกของบทนี้คือไฟล์ unoriented graphเนื่องจากไม่มีลูกศรบนกิ่งก้านของกราฟนั้น

Subgraph และประเภท

ส่วนหนึ่งของกราฟเรียกว่าเป็นไฟล์ subgraph. เราได้รับกราฟย่อยโดยการลบโหนดและ / หรือกิ่งก้านของกราฟที่กำหนด ดังนั้นจำนวนสาขาและ / หรือโหนดของกราฟย่อยจะน้อยกว่ากราฟดั้งเดิม ดังนั้นเราสามารถสรุปได้ว่ากราฟย่อยเป็นส่วนย่อยของกราฟ

ต่อไปนี้คือไฟล์ two types ของย่อหน้าย่อย

Tree
Co-Tree

ต้นไม้

Tree คือกราฟย่อยที่เชื่อมต่อกันของกราฟที่กำหนดซึ่งมีโหนดทั้งหมดของกราฟ แต่ไม่ควรมีการวนซ้ำใด ๆ ในย่อหน้านั้น กิ่งก้านของต้นไม้เรียกว่าtwigs.

พิจารณาสิ่งต่อไปนี้ connected subgraph ของกราฟซึ่งแสดงในตัวอย่างจุดเริ่มต้นของบทนี้

กราฟย่อยที่เชื่อมต่อนี้ประกอบด้วยโหนดทั้งสี่ของกราฟที่กำหนดและไม่มีการวนซ้ำ ดังนั้นจึงเป็นTree.

ต้นไม้นี้มีเพียงสามกิ่งจากหกกิ่งของกราฟที่กำหนด เพราะถ้าเราพิจารณาแม้แต่กิ่งก้านเดียวของกราฟที่เหลืออยู่ก็จะมีการวนซ้ำในกราฟย่อยที่เชื่อมต่อด้านบน จากนั้นกราฟย่อยที่เชื่อมต่อผลลัพธ์จะไม่เป็น Tree

จากต้นไม้ข้างต้นเราสามารถสรุปได้ว่า number of branches ที่มีอยู่ในต้นไม้ควรเท่ากับ n - 1 โดยที่ 'n' คือจำนวนโหนดของกราฟที่กำหนด

ต้นไม้ร่วม

Co-Tree เป็นกราฟย่อยซึ่งเกิดขึ้นพร้อมกับกิ่งก้านที่ถูกลบออกในขณะที่สร้างต้นไม้ ดังนั้นจึงเรียกว่าเป็นComplementของต้นไม้ สำหรับต้นไม้ทุกต้นจะมี Co-Tree ที่สอดคล้องกันและกิ่งก้านของมันจะถูกเรียกว่าเป็นlinksหรือคอร์ด โดยทั่วไปลิงก์จะแสดงด้วยเส้นประ

Co-Tree ที่สอดคล้องกับ Tree ด้านบนจะแสดงในรูปต่อไปนี้

Co-Tree นี้มีเพียงสามโหนดแทนที่จะเป็นสี่โหนดของกราฟที่กำหนดเนื่องจากโหนด 4 ถูกแยกจาก Co-Tree ด้านบน ดังนั้น Co-Tree จึงไม่จำเป็นต้องเป็นกราฟย่อยที่เชื่อมต่อกัน Co-Tree นี้มีสามสาขาและรวมกันเป็นวง

number of branchesที่มีอยู่ในต้นไม้ร่วมจะเท่ากับผลต่างระหว่างจำนวนกิ่งก้านของกราฟที่กำหนดกับจำนวนกิ่งไม้ ในทางคณิตศาสตร์สามารถเขียนเป็น

$$ l = b - (n - 1) $$

$$ l = b - n + 1 $$

ที่ไหน