ค่าการเชื่อมต่อเชิงพีชคณิต (หรือที่รู้จักกันในชื่อค่า Fiedlerหรือ ค่า eigenvalue ^ของ Fiedlerตามชื่อของMiroslav Fiedler ) ของกราฟG คือ ค่า eigenvalueที่เล็กที่สุดเป็นอันดับสอง(นับค่า eigenvalue หลายค่าแยกกัน) ของเมทริกซ์ LaplacianของG [ ^{1 ]}ค่า eigenvalue นี้จะมากกว่า 0 ก็ต่อเมื่อGเป็นกราฟที่เชื่อมต่อกันนี่เป็นผลสืบเนื่องมาจากข้อเท็จจริงที่ว่าจำนวนครั้งที่ 0 ปรากฏเป็นค่า eigenvalue ในเมทริกซ์ Laplacian คือจำนวนส่วนประกอบที่เชื่อมต่อกันในกราฟ ขนาดของค่านี้สะท้อนให้เห็นว่ากราฟโดยรวมเชื่อมต่อกันได้ดีเพียงใด มีการใช้ค่านี้ในการวิเคราะห์ความทนทานและ ความสามารถในการซิง โครไนซ์ของเครือข่าย

การเชื่อมต่อเชิงพีชคณิตของกราฟแบบไม่มีทิศทางที่มีน้ำหนักไม่เป็นลบคือโดยความไม่เท่าเทียมกันจะเป็นแบบเข้มงวดก็ต่อเมื่อGเป็นกราฟที่เชื่อมต่อกัน อย่างไรก็ตาม การเชื่อมต่อเชิงพีชคณิตอาจเป็นลบได้สำหรับกราฟแบบมีทิศทางทั่วไป แม้ว่าGจะเป็นกราฟที่เชื่อมต่อกันก็ตาม^{[ 2 ]}ยิ่งไปกว่านั้น ค่าของการเชื่อมต่อเชิงพีชคณิตจะถูกจำกัดค่าสูงสุดโดยการเชื่อมต่อ แบบดั้งเดิม (จุดยอด) ของกราฟเว้นแต่ว่ากราฟจะเป็นกราฟสมบูรณ์ (การเชื่อมต่อเชิงพีชคณิตของกราฟสมบูรณ์K _nคืออันดับn ของมัน ) ^{[ 3 ]}สำหรับกราฟแบบไม่มีทิศทางที่เชื่อมต่อกันซึ่งมีน้ำหนักขอบไม่เป็นลบ จุดยอด nจุด และเส้นผ่านศูนย์กลางDการเชื่อมต่อเชิงพีชคณิตยังเป็นที่ทราบกันว่าถูกจำกัดค่าต่ำสุดโดย[ ^{4 ​​] และ}ในความเป็นจริง (ในผลลัพธ์ที่เกิดจากBrendan McKay ) โดย^{[ 5 ]}สำหรับกราฟตัวอย่างที่มี 6 โหนดดังที่แสดงด้านบน ( ) ขอบเขตเหล่านี้จะคำนวณได้ดังนี้: แตกต่างจากรูปแบบดั้งเดิมของการเชื่อมต่อกราฟซึ่งกำหนดโดยการกำหนดค่าเฉพาะที่ซึ่งการลบจะทำให้กราฟขาดการเชื่อมต่อ การเชื่อมต่อเชิงพีชคณิตขึ้นอยู่กับจำนวนจุดยอดโดยรวม เช่นเดียวกับวิธีที่จุดยอดเชื่อมต่อกัน ในกราฟแบบสุ่มการเชื่อมต่อเชิงพีชคณิตจะลดลงตามจำนวนจุดยอด และเพิ่มขึ้นตามระดับเฉลี่ย^{[ 6 ]}${\displaystyle a(G)\geq 0}$${\displaystyle {\text{การเชื่อมต่อเชิงพีชคณิต}}\leq {\text{การเชื่อมต่อ}}}$${\textstyle {\frac {1}{nD}}}$${\textstyle {\frac {4}{nD}}}$${\textstyle n=6,D=3}$$${\displaystyle 4/18=0.222\leq {\text{การเชื่อมต่อเชิงพีชคณิต 0.722}}\leq {\text{การเชื่อมต่อ 1.}}}$$

นิยามที่แน่นอนของการเชื่อมต่อเชิงพีชคณิตขึ้นอยู่กับประเภทของลาปลาเซียนที่ใช้ฟาน ชุงได้พัฒนาทฤษฎีที่ครอบคลุมโดยใช้ลาปลาเซียนเวอร์ชันที่ปรับขนาดใหม่ ซึ่งขจัดความขึ้นอยู่กับจำนวนจุดยอด ดังนั้นขอบเขตจึงแตกต่างกันเล็กน้อย^{[ 7 ]}

ในแบบจำลองการซิงโครไนซ์บนเครือข่าย เช่นแบบจำลอง Kuramotoเมทริกซ์ Laplacian เกิดขึ้นเองตามธรรมชาติ ดังนั้นการเชื่อมต่อเชิงพีชคณิตจึงบ่งชี้ว่าเครือข่ายจะซิงโครไนซ์ได้ง่ายเพียงใด^{[ 8 ]}มาตรการอื่นๆ เช่นระยะทาง เฉลี่ย (ความยาวเส้นทางลักษณะเฉพาะ) ก็สามารถนำมาใช้ได้เช่นกัน^{[ 9 ]}และในความเป็นจริง การเชื่อมต่อเชิงพีชคณิตมีความสัมพันธ์อย่างใกล้ชิดกับระยะทางเฉลี่ย (ส่วนกลับของระยะทางเฉลี่ย) ^{[ 5 ]}

การเชื่อมต่อเชิงพีชคณิตยังเกี่ยวข้องกับคุณลักษณะการเชื่อมต่ออื่นๆ เช่นจำนวนไอโซเพอริเมตริกซึ่งถูกจำกัดด้านล่างด้วยครึ่งหนึ่งของการเชื่อมต่อเชิงพีชคณิต^{[ 10 ]}

ทฤษฎีดั้งเดิมที่เกี่ยวข้องกับการเชื่อมต่อเชิงพีชคณิตถูกสร้างขึ้นโดยMiroslav Fiedler [ ^{11 ] [ 12 ] เพื่อ}เป็นเกียรติแก่เขาเวกเตอร์ลักษณะเฉพาะที่เกี่ยวข้องกับการเชื่อมต่อเชิงพีชคณิตจึงถูกตั้งชื่อว่าเวกเตอร์ Fiedlerเวกเตอร์ Fiedler สามารถใช้ในการแบ่งกราฟได้

สำหรับกราฟตัวอย่างในส่วนบทนำ เวกเตอร์ Fiedler คือค่าลบจะสัมพันธ์กับจุดยอดที่เชื่อมต่อไม่ดี (จุดยอด 6) และจุดเชื่อมต่อ ที่อยู่ใกล้เคียง (จุดยอด 4) ในขณะที่ค่าบวกจะสัมพันธ์กับจุดยอดอื่นๆ ดังนั้น เครื่องหมายของค่าในเวกเตอร์ Fiedler สามารถใช้แบ่งกราฟนี้ออกเป็นสองส่วนได้ คือหรืออีกทางหนึ่ง ค่า 0.069 (ซึ่งใกล้เคียงกับศูนย์) สามารถจัดอยู่ในกลุ่มของตัวเอง แบ่งกราฟออกเป็นสามส่วน คือหรือย้ายไปยังส่วนแบ่งอีกส่วนหนึ่งดังภาพ ค่ากำลังสองของส่วนประกอบของเวกเตอร์ Fiedler ซึ่งรวมกันได้เท่ากับหนึ่งเนื่องจากเวกเตอร์ได้รับการทำให้เป็นมาตรฐาน สามารถตีความได้ว่าเป็นความน่าจะเป็นของจุดข้อมูลที่สอดคล้องกันที่จะถูกกำหนดให้กับส่วนแบ่งตามเครื่องหมาย ${\textstyle {\begin{pmatrix}0.415&0.309&0.069&-0.221&0.221&-0.794\end{pmatrix}}}$${\textstyle \{1,2,3,5\},\{4,6\}}$${\textstyle \{1,2,5\},\{3\},\{4,6\}}$${\textstyle \{1,2,5\},\{3,4,6\}}$

• การเชื่อมต่อ (ทฤษฎีกราฟ)
• คุณสมบัติของกราฟ