ทฤษฎีกราฟ - พื้นฐาน

กราฟคือแผนภาพของจุดและเส้นที่เชื่อมต่อกับจุด มีอย่างน้อยหนึ่งบรรทัดที่เชื่อมต่อกับชุดของจุดยอดสองจุดโดยไม่มีจุดยอดเชื่อมต่อตัวเอง แนวคิดของกราฟในทฤษฎีกราฟขึ้นอยู่กับคำพื้นฐานบางคำเช่นจุดเส้นจุดยอดขอบองศาของจุดยอดคุณสมบัติของกราฟเป็นต้นในบทนี้เราจะกล่าวถึงพื้นฐานของทฤษฎีกราฟเหล่านี้

จุด

A pointคือตำแหน่งเฉพาะในปริภูมิหนึ่งมิติสองมิติหรือสามมิติ เพื่อความเข้าใจที่ดีขึ้นจุดสามารถแสดงด้วยตัวอักษร สามารถแทนด้วยจุด

ตัวอย่าง

จุดนี้คือจุดชื่อ 'a'

ไลน์

ก Lineเป็นการเชื่อมต่อระหว่างสองจุด สามารถแสดงด้วยเส้นทึบ

Example

ที่นี่ 'a' และ 'b' คือจุด จุดเชื่อมระหว่างสองจุดนี้เรียกว่าเส้น

จุดยอด

จุดยอดคือจุดที่เส้นหลายเส้นมาบรรจบกัน เรียกอีกอย่างว่าnode. เช่นเดียวกับจุดจุดยอดยังแสดงด้วยตัวอักษร

Example

ที่นี่จุดยอดถูกตั้งชื่อด้วยตัวอักษร 'a'

ขอบ

edge คือคำศัพท์ทางคณิตศาสตร์สำหรับเส้นที่เชื่อมต่อจุดยอดสองจุด ขอบจำนวนมากสามารถเกิดขึ้นจากจุดยอดเดียว หากไม่มีจุดยอดจะไม่สามารถสร้างขอบได้ ต้องมีจุดยอดเริ่มต้นและจุดยอดสิ้นสุดสำหรับขอบ

Example

ที่นี่ 'a' และ 'b' คือจุดยอดสองจุดและจุดเชื่อมระหว่างพวกเขาเรียกว่าขอบ

กราฟ

กราฟ 'G' ถูกกำหนดให้เป็น G = (V, E) โดยที่ V คือชุดของจุดยอดทั้งหมดและ E คือชุดของขอบทั้งหมดในกราฟ

Example 1

ในตัวอย่างข้างต้น ab, ac, cd และ bd คือขอบของกราฟ ในทำนองเดียวกัน a, b, c และ d คือจุดยอดของกราฟ

Example 2

ในกราฟนี้มีจุดยอด a, b, c และ d สี่จุดและสี่ขอบ ab, ac, ad และ cd

วน

ในกราฟถ้าขอบวาดจากจุดยอดถึงตัวมันเองจะเรียกว่าลูป

Example 1

ในกราฟด้านบน V คือจุดยอดซึ่งมีขอบ (V, V) เป็นรูปวง

Example 2

ในกราฟนี้มีสองลูปซึ่งเกิดขึ้นที่จุดยอด a และจุดยอด b

ระดับของจุดยอด

มันคือจำนวนจุดยอดที่อยู่ติดกับจุดยอด V

Notation - องศา (V)

ในกราฟธรรมดาที่มีจุดยอดจำนวน n ระดับของจุดยอดใด ๆ คือ -

องศา (v) ≤ n - 1 ∀ v ∈ G

จุดยอดสามารถสร้างขอบกับจุดยอดอื่น ๆ ทั้งหมดยกเว้นด้วยตัวมันเอง ดังนั้นระดับของจุดยอดจะขึ้นอยู่กับnumber of vertices in the graph minus 1. 1 นี้มีไว้สำหรับจุดยอดในตัวเองเนื่องจากไม่สามารถสร้างลูปด้วยตัวเองได้ หากมีการวนซ้ำที่จุดยอดใด ๆ แสดงว่าไม่ใช่กราฟแบบง่าย

ระดับของจุดยอดสามารถพิจารณาได้ภายใต้กราฟสองกรณี -

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

ระดับของจุดยอดในกราฟที่ไม่ได้บอกทิศทาง

กราฟที่ไม่มีทิศทางไม่มีขอบกำกับ ลองพิจารณาตัวอย่างต่อไปนี้

Example 1

ดูกราฟต่อไปนี้ -

ในกราฟ Undirected ข้างต้น

deg (a) = 2 เนื่องจากมี 2 edge มาพบกันที่จุดยอด 'a'
deg (b) = 3 เนื่องจากมีขอบ 3 ด้านมาบรรจบกันที่จุดยอด 'b'
deg (c) = 1 เนื่องจากมีขอบ 1 เกิดขึ้นที่จุดยอด 'c'
ดังนั้น 'c' คือ a pendent vertex.
deg (d) = 2 เนื่องจากมี 2 ขอบมาบรรจบกันที่จุดยอด 'd'
deg (e) = 0 เนื่องจากมีขอบ 0 เกิดขึ้นที่จุดยอด 'e'
ดังนั้น 'e' จึงเป็นไฟล์ isolated vertex.

Example 2

ดูกราฟต่อไปนี้ -

ในกราฟด้านบน

deg (a) = 2, deg (b) = 2, deg (c) = 2, deg (d) = 2 และ deg (e) = 0

จุดยอด 'e' เป็นจุดยอดที่แยกได้ กราฟไม่มีจุดยอดจี้ใด ๆ

ระดับของจุดยอดในกราฟกำกับ

ในกราฟกำกับจุดยอดแต่ละจุดจะมี indegree และ outdegree.

ดัชนีของกราฟ

Indegree ของจุดยอด V คือจำนวนขอบที่เข้ามาในจุดยอด V
Notation - deg− (V)

ค่ามาตรฐานของกราฟ

Outdegree ของจุดยอด V คือจำนวนขอบที่ยื่นออกไปจากจุดยอด V
Notation - องศา + (V)

ลองพิจารณาตัวอย่างต่อไปนี้

Example 1

ดูกราฟกำกับต่อไปนี้ Vertex 'a' มีสองขอบ 'ad' และ 'ab' ซึ่งจะออกไปด้านนอก ดังนั้นค่าสูงสุดของมันคือ 2 ในทำนองเดียวกันมีขอบ 'ga' มาทางจุดยอด 'a' ดังนั้นดัชนีของ 'a' คือ 1

ดัชนีและจุดสูงสุดของจุดยอดอื่น ๆ แสดงไว้ในตารางต่อไปนี้ -

จุดยอด	Indegree	ปริญญาตรี
ก	1	2
ข	2	0
ค	2	1
ง	1	1
จ	1	1
ฉ	1	1
ก	0	2

Example 2

ดูกราฟกำกับต่อไปนี้ จุดยอด 'a' มีขอบ 'ae' ออกไปจากจุดยอด 'a' ดังนั้นค่า outdegree คือ 1 ในทำนองเดียวกันกราฟจะมีขอบ 'ba' มาทางจุดยอด 'a' ดังนั้นดัชนีของ 'a' คือ 1

ดัชนีและจุดสูงสุดของจุดยอดอื่น ๆ แสดงไว้ในตารางต่อไปนี้ -

จุดยอด	Indegree	ปริญญาตรี
ก	1	1
ข	0	2
ค	2	0
ง	1	1
จ	1	1

Pendent Vertex

ด้วยการใช้องศาของจุดยอดเรามีจุดยอดพิเศษสองประเภท จุดยอดที่มีดีกรีหนึ่งเรียกว่าจุดยอดแบบจี้

Example

ในตัวอย่างนี้จุดยอด 'a' และจุดยอด 'b' มีขอบเชื่อมต่อ 'ab' ดังนั้นในส่วนที่เกี่ยวกับจุดยอด 'a' จึงมีขอบเพียงด้านเดียวที่นำไปสู่จุดยอด 'b' และในทำนองเดียวกันเมื่อเทียบกับจุดยอด 'b' มีขอบเพียงด้านเดียวเท่านั้นที่ไปสู่จุดยอด 'a' สุดท้ายจุดยอด 'a' และจุดยอด 'b' มีระดับเป็นหนึ่งซึ่งเรียกอีกอย่างว่าจุดยอดจี้

จุดยอดที่แยกได้

จุดยอดที่มีองศาศูนย์เรียกว่าจุดยอดแยก

Example

ที่นี่จุดยอด 'a' และจุดยอด 'b' ไม่มีการเชื่อมต่อระหว่างกันและยังจุดยอดอื่น ๆ ดังนั้นระดับของจุดยอดทั้งสอง 'a' และ 'b' จึงเป็นศูนย์ สิ่งเหล่านี้เรียกอีกอย่างว่าจุดยอดแยก

Adjacency

นี่คือบรรทัดฐานของ adjacency -

ในกราฟจะมีจุดยอด 2 จุด adjacentถ้ามีขอบระหว่างจุดยอดทั้งสอง ที่นี่ความใกล้เคียงของจุดยอดจะถูกคงไว้โดยขอบด้านเดียวที่เชื่อมต่อจุดยอดทั้งสองนั้น
ในกราฟกล่าวว่าสองขอบอยู่ติดกันหากมีจุดยอดทั่วไประหว่างขอบทั้งสอง ที่นี่ความใกล้ชิดของขอบจะถูกรักษาโดยจุดยอดเดียวที่เชื่อมต่อสองขอบ

Example 1