ในทางคณิตศาสตร์ทฤษฎีกราฟเชิงสเปกตรัมคือการศึกษาคุณสมบัติของกราฟที่สัมพันธ์กับพหุนามลักษณะเฉพาะค่าลักษณะเฉพาะและเวกเตอร์ลักษณะเฉพาะของเมทริกซ์ที่เกี่ยวข้องกับกราฟ เช่นเมทริกซ์ประชิดหรือเมทริกซ์ลาปลาเซียน

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

แม้ว่าเมทริกซ์ประชิดจะขึ้นอยู่กับการกำหนดป้ายกำกับจุดยอด แต่สเปกตรัม ของมัน เป็นค่าคงที่ของกราฟแม้จะไม่ใช่ค่าคง ที่ที่สมบูรณ์ ก็ตาม

ทฤษฎีกราฟเชิงสเปกตรัมยังเกี่ยวข้องกับพารามิเตอร์ของกราฟซึ่งกำหนดโดยความซ้ำซ้อนของค่าลักษณะเฉพาะของเมทริกซ์ที่เกี่ยวข้องกับกราฟ เช่นจำนวนโคลิน เดอ แวร์ดิแยร์

กราฟสองกราฟเรียกว่ามีสเปกตรัมร่วมกันหรือมีสเปกตรัมเหมือนกันหากเมทริกซ์ประชิดของกราฟทั้งสองมีสเปกตรัมเหมือนกันกล่าวคือ เมทริกซ์ประชิดมีค่าลักษณะเฉพาะ (eigenvalue) เดียวกันและมีจำนวนเท่าเดิม

กราฟที่มีสเปกตรัมร่วมกันไม่จำเป็นต้องเป็น กราฟ ที่สมมาตรกันแต่กราฟที่สมมาตรกันจะมีสเปกตรัมร่วมกันเสมอ

กล่าวได้ว่ากราฟหนึ่ง ถูกกำหนดโดยสเปกตรัมของมัน ถ้ากราฟอื่นใดที่มีสเปกตรัมเดียวกันกับกราฟ นั้นเป็นไอโซมอร์ฟิกกับกราฟนั้น ${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$

ตัวอย่างแรกๆ ของกลุ่มกราฟที่ถูกกำหนดโดยสเปกตรัม ได้แก่:

• กราฟทั้งหมด​
• ต้นไม้รูปดาวที่มีขอบเขตจำกัด

กล่าวกันว่ากราฟสองกราฟเป็นคู่สเปกตรัมเดียวกัน หากกราฟทั้งสองมีสเปกตรัมเดียวกันแต่ไม่ใช่กราฟสมมาตรกัน

คู่โคสเปกตรัมที่เล็กที่สุดคือ { K _1,4 , C ₄ ∪ K _{1 } ซึ่งประกอบด้วย} ดาว 5 จุดยอดและกราฟรวม ของ วงจร 4 จุดยอดและกราฟจุดยอดเดียว^{[ 1 ]}ตัวอย่างแรกของกราฟโคสเปกตรัมได้รับการรายงานโดย Collatz และ Sinogowitz ^{[ 2 ]}ในปี พ.ศ. 2490

คู่ที่เล็กที่สุดของ คู่โคสเปกตรัม ทรงหลายเหลี่ยมคือเอนนาเฮดราที่มีจุดยอดแปดจุดในแต่ละอัน^{[ 3 ]}

ต้นไม้เกือบทั้งหมดมีสเปกตรัมร่วมกัน กล่าวคือ เมื่อจำนวนจุดยอดเพิ่มขึ้น สัดส่วนของต้นไม้ที่มีต้นไม้ที่มีสเปกตรัมร่วมกันจะเข้าใกล้ 1 ^{[ 4 ]}

กราฟปกติสองกราฟจะมีสเปกตรัมร่วมกันก็ต่อเมื่อกราฟส่วนเติมเต็มของกราฟทั้งสองนั้นมีสเปกตรัมร่วมกัน^{[ 5 ]}

กราฟระยะทางสม่ำเสมอสอง กราฟ จะมีสเปกตรัมร่วมกันก็ต่อเมื่อมีอาร์เรย์จุดตัดเดียวกัน

^{กราฟโคสเปกตรัมยังสามารถสร้าง ได้}โดยใช้วิธี Sunada [ ^{6 ]}

แหล่งที่มาสำคัญอีกแหล่งหนึ่งของกราฟโคสเปกตรัมคือกราฟจุดร่วมเส้นตรงและกราฟจุดตัดของเรขาคณิตจุด-เส้นตรงกราฟเหล่านี้มักเป็นโคสเปกตรัม แต่มักจะไม่เป็นไอโซมอร์ฟิก^{[ 7 ]}

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

ค่าคงที่ชีเกอร์ (หรือเรียกอีกอย่างว่าเลขชีเกอร์หรือเลขไอโซเพอริเมตริก ) ของกราฟเป็นค่าตัวเลขที่ใช้วัดว่ากราฟนั้นมี "คอขวด" หรือไม่ ค่าคงที่ชีเกอร์ในฐานะตัววัด "ความเป็นคอขวด" มีความสำคัญอย่างมากในหลายสาขา เช่น การสร้างเครือข่ายคอมพิวเตอร์ ที่มีการเชื่อมต่อที่ดี การสับไพ่และโทโพโลยีมิติที่ต่ำ (โดยเฉพาะอย่างยิ่ง การศึกษาไฮเปอร์โบลิก 3- แมนิโฟลด์ )

กล่าวอย่างเป็นทางการมากขึ้น ค่าคงที่ Cheeger h ( G ) ของกราฟGบน จุดยอด nจุด ถูกกำหนดดังนี้

${\displaystyle h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial (S)|}{|S|}},}$

โดยที่ค่าต่ำสุดจะอยู่เหนือเซตS ที่ไม่ว่างทั้งหมดที่ ^มี จุดยอด ไม่เกินn /2 และ ∂( S ) คือขอบเขตขอบของSกล่าวคือ เซตของขอบที่มีจุดปลายเพียงจุดเดียวในS [ ^{8 ]}

เมื่อกราฟGเป็นd-ปกติ จะมีความสัมพันธ์ระหว่างh ( G ) และช่องว่างสเปกตรัมd − λ ₂ของGอสมการเนื่องจาก Dodziuk ^{[ 9 ]}และAlonและMilman ^{[ 10 ]}ระบุว่า^{[ 11 ]}

${\displaystyle {\frac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.}$

ความไม่เท่าเทียมกันนี้มีความเกี่ยวข้องอย่างใกล้ชิดกับขอบเขตของ Cheegerสำหรับลูกโซ่ Markovและสามารถมองได้ว่าเป็นเวอร์ชันแบบไม่ต่อเนื่องของความไม่เท่าเทียมกันของ Cheegerในเรขาคณิตแบบ Riemannian

สำหรับกราฟที่เชื่อมต่อกันทั่วไปซึ่งไม่จำเป็นต้องเป็นกราฟปกติ ความไม่เท่าเทียมกันทางเลือกอื่นจะกำหนดโดย Chung ^{[ 12 ] : 35}

${\displaystyle {\frac {1}{2}}{\lambda }\leq {\mathbf {h} }(G)\leq {\sqrt {2\lambda }},}$

โดยที่คือค่าไอเกนที่ไม่เป็นศูนย์น้อยที่สุดของตัวดำเนินการลาปลาเซียนแบบนอร์มาไลซ์ และคือค่าคงที่ชีเกอร์ (แบบนอร์มาไลซ์) ${\displaystyle \lambda }$${\displaystyle {\mathbf {h} }(G)}$

${\displaystyle {\mathbf {h} }(G)=\min _{\emptyset \not =S\subset V(G)}{\frac {|\partial (S)|}{\min({\mathrm {vol} }(S),{\mathrm {vol} }({\bar {S}}))}}}$

โดยที่ผลรวมของดีกรีของจุดยอดใน คือ. ${\displaystyle {\mathrm {vol} }(Y)}$${\displaystyle Y}$

มีขอบเขตค่าลักษณะเฉพาะสำหรับเซตอิสระในกราฟปกติซึ่งเดิมทีเป็นผลงานของAlan J. Hoffmanและ Philippe Delsarte ^{[ 13 ]}

สมมติว่าเป็นกราฟปกติที่มีจุดยอดจำนวน n จุด และมีค่าไอเกนน้อยที่สุดเท่ากับn ดังนั้น: โดยที่แทนจำนวนอิสระ ของ กราฟ ${\displaystyle G}$${\displaystyle k}$${\displaystyle n}$${\displaystyle \lambda _{\mathrm {min} }}$$${\displaystyle \alpha (G)\leq {\frac {n}{1-{\frac {k}{\lambda _{\mathrm {min} }}}}}}$$${\displaystyle \alpha (G)}$

ขอบเขตนี้ได้รับการนำไปใช้เพื่อสร้างการพิสูจน์เชิงพีชคณิตของทฤษฎีบท Erdős–Ko–Radoและทฤษฎีบทที่คล้ายคลึงกันสำหรับกลุ่มย่อยที่ตัดกันเหนือฟิลด์จำกัด^{[ 14 ]}

สำหรับกราฟทั่วไปที่ไม่จำเป็นต้องเป็นกราฟปกติ ขอบเขตบนที่คล้ายกันสำหรับจำนวนความเป็นอิสระสามารถหาได้โดยใช้ค่าไอเกนสูงสุด ของลาปลาเซียนปกติ^{[ 12 ]}ของ: โดยที่และแทนดีกรีสูงสุดและต่ำสุดในตามลำดับ นี่เป็นผลมาจากความไม่เท่าเทียมกันทั่วไปมากขึ้น (หน้า 109 ใน ^{[ 12 ]} ): โดยที่เป็นเซตอิสระของจุดยอด และแทนผลรวมของดีกรีของจุดยอดใน ${\displaystyle \lambda '_{max}}$${\displaystyle G}$$${\displaystyle \alpha (G)\leq n(1-{\frac {1}{\lambda '_{\mathrm {max} }}}){\frac {\mathrm {maxdeg} }{\mathrm {mindeg} }}}$$${\displaystyle {\คณิตศาสตร์ {maxdeg} }}$${\displaystyle {\คณิตศาสตร์ {mindeg} }}$${\displaystyle G}$$${\displaystyle {\mathrm {vol} }(X)\leq (1-{\frac {1}{\lambda '_{\mathrm {max} }}}){\mathrm {vol} }(V(G))}$$${\displaystyle X}$${\displaystyle {\mathrm {vol} }(Y)}$${\displaystyle Y}$

ทฤษฎีกราฟเชิงสเปกตรัมเกิดขึ้นในทศวรรษ 1950 และ 1960 นอกจาก การวิจัย ทฤษฎีกราฟเกี่ยวกับความสัมพันธ์ระหว่างคุณสมบัติเชิงโครงสร้างและเชิงสเปกตรัมของกราฟแล้ว แหล่งที่มาสำคัญอีกแหล่งหนึ่งคือการวิจัยในเคมีควอนตัมแต่ความเชื่อมโยงระหว่างงานทั้งสองสายนี้ยังไม่ถูกค้นพบจนกระทั่งอีกนานต่อมา^{[ 15 ]}หนังสือSpectra of Graphs ^{[ 16 ]} ในปี 1980 โดย Cvetković, Doob และ Sachs ได้สรุปงานวิจัยเกือบทั้งหมดในสาขานี้จนถึงปัจจุบัน ในปี 1988 ได้มีการปรับปรุงโดยการสำรวจRecent Results in the Theory of Graph Spectra [ ^{17 ] หนังสือ} Spectra of Graphsฉบับที่ 3 (1995) มีบทสรุปของผลงานล่าสุดเพิ่มเติมในหัวข้อนี้^{[ 15 ]}

สาขาการวิเคราะห์ทางเรขาคณิตแบบไม่ต่อเนื่อง ซึ่งสร้างและพัฒนาโดยToshikazu Sunadaในช่วงทศวรรษ 2000 เกี่ยวข้องกับทฤษฎีกราฟสเปกตรัมในแง่ของ Laplacian แบบไม่ต่อเนื่องที่เกี่ยวข้องกับกราฟถ่วงน้ำหนัก^{[ 18 ]}มีการนำไปประยุกต์ใช้ในสาขาอื่นๆ อีกมากมาย รวมถึง การ วิเคราะห์ รูปร่าง

การพัฒนาล่าสุดในทฤษฎีกราฟสเปกตรัมคือการวิเคราะห์ความถี่จุดยอด ซึ่งเป็นชุดเทคนิคสำหรับการแก้ปัญหาในแอปพลิเคชันในชีวิตจริงหลายอย่าง เช่นการประมวลผลสัญญาณ^{[ 19 ] [ 20 ] [ 21 ] [ 22 ]}

• กราฟปกติอย่างมาก
• การเชื่อมต่อเชิงพีชคณิต
• ทฤษฎีกราฟเชิงพีชคณิต
• การจัดกลุ่มสเปกตรัม
• การวิเคราะห์รูปร่างสเปกตรัม
• ดัชนีเอสตราดา
• โลวาซ เธต้า
• กราฟขยาย

• สปีลแมน, แดเนียล (2011). "ทฤษฎีกราฟเชิงสเปกตรัม" (PDF )[บทจากหนังสือ Combinatorial Scientific Computing]
• สปีลแมน, แดเนียล (2007). "ทฤษฎีกราฟเชิงสเปกตรัมและการประยุกต์ใช้ "[นำเสนอในการประชุม FOCS 2007]
• สปีลแมน, แดเนียล (2004). "ทฤษฎีกราฟเชิงสเปกตรัมและการประยุกต์ใช้ "[หน้าข้อมูลหลักสูตรและเอกสารประกอบการบรรยาย]