ในทฤษฎีกราฟซึ่งเป็นสาขาหนึ่งของคณิตศาสตร์กราฟมัธยฐานคือกราฟแบบไม่มีทิศทางที่จุดยอด สามจุด , , และ ทุก ๆ สามจุด จะมีจุดมัธยฐาน ที่ไม่ซ้ำกันเพียงจุดเดียว นั่นคือ จุดยอดที่อยู่ในเส้นทางที่สั้นที่สุดระหว่างแต่ละคู่ของ, , และ ${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle m(a,b,c)}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$

แนวคิดของกราฟมัธยฐานได้รับการศึกษามานานแล้ว เช่น โดยBirkhoff & Kiss (1947)หรือ (โดยชัดเจนยิ่งขึ้น) โดยAvann (1961)แต่บทความแรกที่เรียกกราฟเหล่านี้ว่า "กราฟมัธยฐาน" ดูเหมือนจะเป็นของNebeský (1971)ดังที่Chung , Grahamและ Saks เขียนไว้ว่า "กราฟมัธยฐานเกิดขึ้นตามธรรมชาติในการศึกษาเซตเรียงลำดับและแลตทิซกระจาย แบบไม่ต่อเนื่อง และมีวรรณกรรมมากมาย" ^{[ 1 ]} ในวิชาพันธุศาสตร์เชิงวิวัฒนาการกราฟ Buneman ที่แสดงถึงต้นไม้วิวัฒนาการแบบประหยัดสูงสุด ทั้งหมด เป็นกราฟมัธยฐาน^{[ 2 ]} กราฟมัธยฐานยังเกิดขึ้นในทฤษฎีการเลือกทางสังคมด้วย หากชุดของทางเลือกมีโครงสร้างของกราฟมัธยฐาน ก็สามารถอนุมานความชอบส่วนใหญ่ในหมู่ทางเลือกเหล่านั้นได้อย่างชัดเจน^{[ 3 ]}

การสำรวจเพิ่มเติมเกี่ยวกับกราฟค่ามัธยฐานมีให้โดยKlavžar & Mulder (1999) , Bandelt & Chepoi (2008)และKnuth (2008 )

ต้นไม้ทุกต้นเป็นกราฟมัธยฐาน เพื่อดูสิ่งนี้ ให้สังเกตว่าในต้นไม้ การรวมกันของเส้นทางที่สั้นที่สุดสามเส้นทางระหว่างคู่ของจุดยอดสามจุด, , และจะเป็นเส้นทางเอง หรือเป็นต้นไม้ย่อยที่เกิดจากเส้นทางสามเส้นทางมาบรรจบกันที่โหนดกลางเดียวที่มีดีกรีสาม ถ้าการรวมกันของเส้นทางทั้งสามเป็นเส้นทางเอง ค่ามัธยฐานจะเท่ากับ, , หรือแล้วแต่ว่าจุดยอดใดในสามจุดนี้อยู่ระหว่างจุดยอดอีกสองจุดในเส้นทาง ถ้าต้นไม้ย่อยที่เกิดจากการรวมกันของเส้นทางทั้งสามไม่ใช่เส้นทาง ค่ามัธยฐานของจุดยอดทั้งสามจะเป็นโหนดกลางที่มีดีกรีสามของต้นไม้ย่อยนั้น^{[ 4 ]}${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle m(a,b,c)}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$

ตัวอย่างเพิ่มเติมของกราฟค่ามัธยฐานมีอยู่ในกราฟกริดในกราฟกริด พิกัดของค่ามัธยฐานสามารถหาได้จากค่ามัธยฐานของพิกัดของ, , และในทางกลับกัน ปรากฏว่าในกราฟค่ามัธยฐานทุกกราฟ เราสามารถกำหนดป้ายกำกับจุดยอดด้วยจุดในแลตทิซจำนวนเต็มในลักษณะที่สามารถคำนวณค่ามัธยฐานตามพิกัดได้ด้วยวิธีนี้^{[ 5 ]}${\displaystyle m(a,b,c)}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$

กราฟ สี่เหลี่ยมจัตุรัสซึ่งเป็นกราฟระนาบที่หน้าภายในทั้งหมดเป็นรูปสี่เหลี่ยมจัตุรัส และจุดยอดภายในทั้งหมดมีขอบที่เชื่อมต่อกันสี่เส้นขึ้นไป ถือเป็นคลาสย่อยอีกคลาสหนึ่งของกราฟมัธยฐาน^{[ 6 ]} โพลีโอมีโนเป็นกรณีพิเศษของกราฟสี่เหลี่ยมจัตุรัส ดังนั้นจึงเป็นกราฟมัธยฐานเช่นกัน^{[ 7 ]}

กราฟซิมเพล็กซ์ ของกราฟแบบไม่มีทิศทางใดๆจะมีจุดยอดสำหรับคลิก ทุกอัน (กราฟย่อยสมบูรณ์) ของ; จุดยอดสองจุดของจะเชื่อมโยงกันด้วยขอบ หากคลิกที่สอดคล้องกันแตกต่างกันหนึ่งจุดยอดของกราฟซิมเพล็กซ์เป็นกราฟมัธยฐานเสมอ ซึ่งค่ามัธยฐานของคลิกสามอันที่กำหนดสามารถสร้างขึ้นได้โดยใช้กฎเสียงข้างมากเพื่อกำหนดว่าควรรวมจุดยอดใดของคลิก^{[ 8 ]}${\displaystyle \kappa (G)}$${\displaystyle G}$${\displaystyle G}$${\displaystyle \kappa (G)}$${\displaystyle G}$

กราฟวงจรที่มีความยาวนอกจากสี่จุดยอดจะไม่ สามารถเป็นกราฟมัธยฐานได้ วงจรดังกล่าวทุกวงจรจะมีจุดยอดสามจุด คือ , , และโดยที่เส้นทางที่สั้นที่สุดสามเส้นทางจะวนรอบวงจรทั้งหมดโดยไม่มีจุดตัดร่วมกัน สำหรับจุดยอดสามจุดดังกล่าว จะไม่มีกราฟมัธยฐาน ${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$

ในกราฟใดๆ สำหรับจุดยอดสองจุดใดๆและจำนวนขอบที่น้อยที่สุดระหว่างจุดยอดทั้งสองเรียกว่าระยะทางซึ่งเขียนแทนด้วยช่วงของจุดยอดที่อยู่บนเส้นทางที่สั้นที่สุดระหว่างและถูกกำหนดให้เป็น ${\displaystyle a}$${\displaystyle b}$${\displaystyle d(x,y)}$${\displaystyle a}$${\displaystyle b}$${\displaystyle I(a,b)=\{\,v\mid d(a,b)=d(a,v)+d(v,b)\,\}.}$

กราฟมัธยฐานถูกกำหนดโดยคุณสมบัติที่ว่า สำหรับจุดยอดสามจุดใดๆ, , และช่วงเวลาเหล่านี้จะตัดกันที่จุดเดียว: ${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$

สำหรับทุก, , และ,${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$

${\displaystyle |I(a,b)\cap I(a,c)\cap I(b,c)|=1.}$

ในทำนองเดียวกัน สำหรับจุดยอดสามจุดทุก ๆ, , และเราสามารถหาจุดยอดได้จุดหนึ่งซึ่ง ระยะทาง ที่ไม่ถ่วงน้ำหนักในกราฟเป็นไปตามสมการ และเป็นจุดยอดเพียงจุดเดียวที่สมการเหล่านี้เป็นจริง ${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle m(a,b,c)}$${\displaystyle {\begin{aligned}d(a,b)&=d{\bigl (}a,m(a,b,c){\bigr )}+d{\bigl (}m(a,b,c),b{\bigr )},\\d(a,c)&=d{\bigl (}a,m(a,b,c){\bigr )}+d{\bigl (}m(a,b,c),c{\bigr )},\\d(b,c)&=d{\bigl (}b,m(a,b,c){\bigr )}+d{\bigl (}m(a,b,c),c{\bigr )},\end{aligned}}}$${\displaystyle m(a,b,c)}$

นอกจากนี้ ยังสามารถกำหนดกราฟมัธยฐานได้ว่าเป็นเซตคำตอบของ ปัญหา 2-satisfiability , เป็น retract ของไฮเปอร์คิวบ์ , เป็นกราฟของพีชคณิตมัธยฐาน จำกัด , เป็นกราฟ Buneman ของระบบแยก Helly และเป็นกราฟของ windex โปรดดูรายละเอียดในส่วนถัดไป ${\displaystyle 2}$

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

ในแลตทิซแบบกระจายการดำเนินการมัธยฐาน ไตรภาค แบบคู่ตัวเองของ Birkhoff ^{[ 9 ]} เป็นไปตามสัจพจน์หลักบางประการ ซึ่งมีร่วมกับมัธยฐาน ปกติ ของตัวเลขในช่วงตั้งแต่ถึงและกับพีชคณิตมัธยฐานโดยทั่วไป ${\displaystyle m(a,b,c)=(a\land b)\lor (a\land c)\lor (b\land c)=(a\lor b)\land (a\lor c)\land (b\lor c),}$${\displaystyle 0}$${\displaystyle 1}$

• ภาวะไร้อำนาจในตนเอง : สำหรับทุกคนและ.${\displaystyle m(a,a,b)=a}$${\displaystyle a}$${\displaystyle b}$
• คุณสมบัติการสลับที่ได้ : สำหรับทุก, , และ.${\displaystyle m(a,b,c)=m(a,c,b)=m(b,a,c)=m(b,c,a)=m(c,a,b)=m(c,b,a)}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$
• คุณสมบัติการแจกแจง : สำหรับทุก, , , , และ.${\displaystyle m(a,m(b,c,d),e)=m(m(a,b,e),c,m(a,d,e))}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle d}$${\displaystyle e}$
• องค์ประกอบเอกลักษณ์ : สำหรับทุกคน${\displaystyle m(0,a,1)=a}$${\displaystyle a}$

กฎการกระจายอาจถูกแทนที่ด้วยกฎการเชื่อมโยง: ^{[ 10 ]}

• ความสัมพันธ์เชิงสัมพันธ์ :${\displaystyle m(x,w,m(y,w,z))=m(m(x,w,y),w,z)}$

การดำเนินการค่ามัธยฐานอาจใช้เพื่อกำหนดแนวคิดของช่วงสำหรับแลตทิซแบบกระจาย: ^{[ 11 ]}$${\displaystyle I(a,b)=\{x\mid m(a,x,b)=x\}=\{x\mid a\land b\leq x\leq a\lor b\}.}$$

กราฟของแลตทิซแบบกระจายจำกัดจะมีขอบระหว่างจุดยอดและเมื่อใดก็ตามที่สำหรับจุดยอดสองจุดใดๆและของกราฟนี้ ช่วงที่กำหนดในแง่ของทฤษฎีแลตทิซข้างต้นประกอบด้วยจุดยอดบนเส้นทางที่สั้นที่สุดจากไปยังและดังนั้นจึงตรงกับช่วงทฤษฎีกราฟที่กำหนดไว้ก่อนหน้านี้ สำหรับองค์ประกอบแลตทิซสามตัวใดๆ, , และคือจุดตัดที่ไม่ซ้ำกันของสามช่วง, , และ^{[ 12 ]} ดังนั้น กราฟของแลตทิซแบบกระจายจำกัดใดๆ จึงเป็นกราฟมัธยฐาน ในทางกลับกัน ถ้ากราฟมัธยฐานมีจุดยอดสองจุดและโดยที่จุดยอดอื่นๆ ทุกจุดอยู่บนเส้นทางที่สั้นที่สุดระหว่างทั้งสอง (เทียบเท่ากับสำหรับทุก) แล้วเราอาจกำหนดแลตทิซแบบกระจายซึ่งและและจะเป็นกราฟของแลตทิซนี้^{[ 13 ]}${\displaystyle a}$${\displaystyle b}$${\displaystyle I(a,b)={a,b}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle I(a,b)}$${\displaystyle a}$${\displaystyle b}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle m(a,b,c)}$${\displaystyle I(a,b)}$${\displaystyle I(a,c)}$${\displaystyle I(b,c)}$${\displaystyle G}$${\displaystyle 0}$${\displaystyle 1}$${\displaystyle m(0,a,1)=a}$${\displaystyle a}$${\displaystyle a\land b=m(a,0,b)}$${\displaystyle a\lor b=m(a,1,b)}$${\displaystyle G}$

Duffus & Rival (1983)อธิบายลักษณะกราฟของแลตทิซแบบกระจายโดยตรงว่าเป็นรีแทร็กต์ของไฮเปอร์คิวบ์ที่รักษาเส้นผ่านศูนย์กลาง โดยทั่วไปแล้ว กราฟมัธยฐานทุกกราฟจะก่อให้เกิดการดำเนินการแบบไตรภาคที่สอดคล้องกับคุณสมบัติเอกลักษณ์ การสลับที่ และการกระจาย แต่เป็นไปได้ว่าไม่มีองค์ประกอบเอกลักษณ์ของแลตทิซแบบกระจาย การดำเนินการแบบไตรภาคทุกการดำเนินการบนเซตจำกัดที่สอดคล้องกับคุณสมบัติทั้งสามนี้ (แต่ไม่จำเป็นต้องมี องค์ประกอบ และ) จะก่อให้เกิดกราฟมัธยฐานในลักษณะเดียวกัน^{[ 14 ]}${\displaystyle m}$${\displaystyle 0}$${\displaystyle 1}$

ในกราฟมัธยฐาน เซตของจุดยอดจะเรียกว่าเป็นเซตแบบนูนถ้าสำหรับจุดยอดสองจุดใดๆที่อยู่ในช่วงทั้งหมดจะเป็นเซตย่อยของ หรือกล่าว อีกนัย หนึ่งคือ เมื่อกำหนดนิยามของช่วงทั้งสองข้างต้นจะเป็นเซตแบบนูนก็ต่อเมื่อมันประกอบด้วยเส้นทางที่สั้นที่สุดระหว่างจุดยอดสองจุด หรือถ้ามันประกอบด้วยค่ามัธยฐานของเซตของจุดสามจุดอย่างน้อยสองจุดที่อยู่ในสังเกตว่าจุดตัดของเซตแบบนูนทุกคู่ก็เป็นเซตแบบนูนเช่นกัน^{[ 15 ]}${\displaystyle S}$${\displaystyle a}$${\displaystyle b}$${\displaystyle S}$${\displaystyle I(a,b)}$${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$

เซตแบบนูนในกราฟมัธยฐานมีคุณสมบัติของเฮลลี : ถ้าเป็นกลุ่มเซตแบบนูนที่ตัดกันเป็นคู่ๆ เซตทั้งหมดในจะมีจุดตัดร่วมกัน^{[ 16 ]}เพราะถ้ามีเซตแบบนูนเพียงสามเซต, , และอยู่ในนั้น โดยที่ อยู่ในจุดตัดของคู่และ, อยู่ในจุดตัดของคู่และ, และอยู่ในจุดตัดของคู่และแล้วเส้นทางที่สั้นที่สุดทุกเส้นจากไปยัง จะต้องอยู่ภายในโดยคุณสมบัติแบบนูน และในทำนองเดียวกัน เส้นทางที่สั้นที่สุดทุกเส้นระหว่างจุดยอดอีกสองคู่จะต้องอยู่ภายในเซตอีกสองเซต แต่เป็นส่วนหนึ่งของเส้นทางระหว่างจุดยอดทั้งสามคู่ ดังนั้นจึงอยู่ภายในเซตทั้งสาม และเป็นส่วนหนึ่งของจุดตัดร่วมกันของเซตเหล่านั้น ถ้ามีเซตแบบนูนมากกว่าสามเซต ผลลัพธ์จะตามมาโดยการอุปมานตามจำนวนเซต เพราะเราสามารถแทนที่เซตคู่ใด ๆ ในด้วยเซตที่ตัดกัน โดยใช้ผลลัพธ์สำหรับเซตสามเซตเพื่อแสดงว่าตระกูลที่ถูกแทนที่ยังคงตัดกันเป็นคู่ ๆ ${\displaystyle F}$${\displaystyle F}$${\displaystyle F}$${\displaystyle S}$${\displaystyle T}$${\displaystyle U}$${\displaystyle a}$${\displaystyle S}$${\displaystyle T}$${\displaystyle b}$${\displaystyle T}$${\displaystyle U}$${\displaystyle c}$${\displaystyle S}$${\displaystyle U}$${\displaystyle a}$${\displaystyle b}$${\displaystyle T}$${\displaystyle m(a,b,c)}$${\displaystyle F}$${\displaystyle F}$

กลุ่มเซตแบบนูนที่มีความสำคัญเป็นพิเศษในกราฟมัธยฐาน ซึ่งมีบทบาทคล้ายกับครึ่งพื้นที่ในปริภูมิยุคลิดได้แก่ เซตต่อไปนี้: ${\displaystyle W_{uv}=\{\,w\mid d(w,u)<d(w,v)\,\}}$

นิยามสำหรับแต่ละขอบของกราฟ กล่าวคือประกอบด้วยจุดยอดที่อยู่ใกล้กว่าหรือเทียบเท่ากับจุดยอดที่เส้นทางที่สั้นที่สุดจากไปยัง ผ่านจุดนั้นเพื่อแสดงว่าเป็นกราฟนูน ให้เป็นเส้นทางที่สั้นที่สุดใดๆ ที่เริ่มต้นและสิ้นสุดภายใน; จากนั้นจะต้องอยู่ภายในด้วย มิฉะนั้น จุดสองจุดและสามารถแสดงได้ (โดยพิจารณาระยะทางที่เป็นไปได้ระหว่างจุดยอด) ว่าเป็นค่ามัธยฐานที่แตกต่างกันของ, , และซึ่งขัดแย้งกับนิยามของกราฟมัธยฐานที่กำหนดให้ค่ามัธยฐานต้องมีเพียงหนึ่งเดียว ดังนั้น จุดยอดแต่ละจุดที่ต่อเนื่องกันบนเส้นทางที่สั้นที่สุดระหว่างจุดยอดสองจุดของจึงอยู่ภายใน ด้วยดังนั้น จึงประกอบด้วยเส้นทางที่สั้นที่สุดทั้งหมดระหว่างจุดยอด ซึ่งเป็นหนึ่งในนิยามของความนูน ${\displaystyle uv}$${\displaystyle W_{uv}}$${\displaystyle u}$${\displaystyle v}$${\displaystyle w}$${\displaystyle v}$${\displaystyle w}$${\displaystyle u}$${\displaystyle W_{uv}}$${\displaystyle w_{1}w_{2}\dots w_{k}}$${\displaystyle W_{uv}}$${\displaystyle w_{2}}$${\displaystyle W_{uv}}$${\displaystyle m_{1}=m(u,w_{1},w_{k})}$${\displaystyle m_{2}=m(m_{1},w_{2},\dots ,w_{k})}$${\displaystyle u}$${\displaystyle w_{1}}$${\displaystyle w_{k}}$${\displaystyle W_{uv}}$${\displaystyle W_{uv}}$${\displaystyle W_{uv}}$

คุณสมบัติของ Helly สำหรับเซตมีบทบาทสำคัญในการกำหนดลักษณะของกราฟมัธยฐานในฐานะที่เป็นคำตอบของกรณี 2-satisfiability ดังต่อไปนี้ ${\displaystyle W_{uv}}$

กราฟมัธยฐานมีความเชื่อมโยงอย่างใกล้ชิดกับเซตคำตอบของ ปัญหา ความพึงพอใจ 2ซึ่งสามารถใช้ทั้งเพื่อกำหนดลักษณะของกราฟเหล่านี้และเพื่อเชื่อมโยงกราฟเหล่านี้กับแผนที่ไฮเปอร์คิวบ์ที่รักษาความประชิด^{[ 17 ]}

ปัญหาความน่าพอใจแบบ 2 เงื่อนไข ประกอบด้วยชุดของตัวแปรบูลีนและชุดของเงื่อนไขซึ่งเป็นข้อจำกัดสำหรับตัวแปรบางคู่ที่กำหนดให้ตัวแปรทั้งสองนั้นต้องหลีกเลี่ยงค่าผสมบางอย่าง โดยปกติแล้ว ปัญหาดังกล่าวจะแสดงในรูปแบบปกติแบบเชื่อมโยง (conjunctive normal form ) ซึ่งแต่ละเงื่อนไขจะแสดงเป็นการ เชื่อมโยง แบบ "หรือ" (disjunction)และชุดข้อจำกัดทั้งหมดจะแสดงเป็นการเชื่อมโยงแบบเชื่อมโยง (conjunction ) ของเงื่อนไข เช่น

${\displaystyle (x_{11}\lor x_{12})\land (x_{21}\lor x_{22})\land \cdots \land (x_{n1}\lor x_{n2})\land \cdots .}$

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

ในทางกลับกัน กราฟมัธยฐานทุกกราฟสามารถแสดงได้ในลักษณะนี้ในฐานะเซตคำตอบของอินสแตนซ์ 2-satisfiability ในการค้นหาการแสดงแทนดังกล่าว ให้สร้างอินสแตนซ์ 2-satisfiability โดยที่ตัวแปรแต่ละตัวอธิบายทิศทางของขอบหนึ่งในกราฟ (การกำหนดทิศทางให้กับขอบทำให้กราฟกลายเป็นกราฟทิศทางแทนที่จะเป็นกราฟไร้ทิศทาง) และข้อจำกัดแต่ละข้ออนุญาตให้ขอบสองขอบมีทิศทางร่วมกันได้ก็ต่อเมื่อมีจุดยอดที่ทิศทางทั้งสองอยู่บนเส้นทางที่สั้นที่สุดจากจุดยอดอื่นไปยังแต่ละจุดยอดของสอดคล้องกับคำตอบของอินสแตนซ์ 2-satisfiability นี้ ซึ่งขอบทั้งหมดมีทิศทางไปยังแต่ละคำตอบของอินสแตนซ์ต้องมาจากจุดยอดบางจุดในลักษณะนี้ โดยที่คือจุดตัดร่วมของเซตสำหรับขอบที่มีทิศทางจากไปยังจุดตัดร่วมนี้มีอยู่เนื่องจากคุณสมบัติของ Helly ของเซต ดังนั้น คำตอบของอินสแตนซ์ 2-satisfiability นี้จึงสอดคล้องกับจุดยอด ของ แบบหนึ่งต่อหนึ่ง${\displaystyle G}$${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$${\displaystyle G}$${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$${\displaystyle W_{uw}}$${\displaystyle w}$${\displaystyle u}$${\displaystyle W_{uw}}$${\displaystyle G}$

การหดตัวของกราฟคือแผนที่รักษาความประชิดจากไปยังกราฟย่อยหนึ่ง^{[ 18 ]}กล่าวโดยละเอียดคือเป็น โฮโมมอร์ฟิซึม ของ กราฟจากไปยังตัวมันเอง โดยที่สำหรับแต่ละจุดยอดในกราฟย่อยภาพของการหดตัวเรียกว่าการหดตัวของ${\displaystyle G}$${\displaystyle G}$${\displaystyle \varphi }$${\displaystyle G}$${\displaystyle \varphi (v)=v}$${\displaystyle v}$${\displaystyle \varphi (G)}$${\displaystyle G}$

การหดตัว (Retractions) เป็นตัวอย่างของแผนที่เมตริก (metric maps) กล่าวคือ ระยะห่างระหว่างและสำหรับทุกและจะมีค่าไม่เกินระยะห่างระหว่างและและจะมีค่าเท่ากันเมื่อใดก็ตามที่และทั้งคู่เป็นสมาชิกของดังนั้น การหดตัวจะต้องเป็นกราฟย่อยแบบไอโซเมตริกของ กล่าวคือ ระยะห่างในการหดตัวจะเท่ากับระยะ ห่าง ใน${\displaystyle \varphi (v)}$${\displaystyle \varphi (w)}$${\displaystyle v}$${\displaystyle w}$${\displaystyle v}$${\displaystyle w}$${\displaystyle v}$${\displaystyle w}$${\displaystyle \varphi (G)}$${\displaystyle G}$${\displaystyle G}$

ถ้าเป็นกราฟมัธยฐาน และ, , และเป็นจุดยอดสามจุดใดๆ ของกราฟการหดตัวจะต้องเป็นมัธยฐานของ, , และดังนั้น จะต้องเท่ากับดังนั้น จึงมีมัธยฐานของจุดยอดทั้งสามจุด และ จะต้องเป็นกราฟมัธยฐานด้วย กล่าวอีกนัยหนึ่ง ตระกูลของกราฟมัธยฐานจะปิดภายใต้การดำเนินการหดตัว^{[ 19 ]}${\displaystyle G}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle \varphi (G)}$${\displaystyle \varphi (m(a,b,c))}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle m(a,b,c)}$${\displaystyle \varphi (G)}$

กราฟไฮเปอร์คิวบ์ซึ่งจุดยอดสอดคล้องกับเวกเตอร์บิต ที่เป็นไปได้ทั้งหมด n บิตและจุดยอดสองจุดจะอยู่ติดกันเมื่อเวกเตอร์บิตที่สอดคล้องกันแตกต่างกันเพียงบิตเดียว เป็นกรณีพิเศษของกราฟกริด n มิติ และดังนั้นจึงเป็นกราฟมัธยฐาน ค่ามัธยฐานของเวกเตอร์บิตสามตัว, , และสามารถคำนวณได้โดยการคำนวณฟังก์ชันเสียงข้างมากของบิตของ, , และ ในแต่ละตำแหน่งบิต เนื่องจากกราฟมัธยฐานปิดภายใต้การหดตัว และรวมถึงไฮเปอร์คิวบ์ ดังนั้นการหดตัวทุกครั้งของไฮเปอร์คิวบ์จึงเป็นกราฟมัธยฐาน ${\displaystyle k}$${\displaystyle k}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$

ในทางกลับกัน กราฟมัธยฐานทุกกราฟจะต้องเป็นการหดตัวของไฮเปอร์คิวบ์^{[ 20 ]}สิ่งนี้อาจเห็นได้จากการเชื่อมโยงที่อธิบายไว้ข้างต้นระหว่างกราฟมัธยฐานและ 2-satisfiability: ให้เป็นกราฟของคำตอบสำหรับอินสแตนซ์ 2-satisfiability โดยไม่เสียความเป็นทั่วไปอินสแตนซ์นี้สามารถกำหนดได้ในลักษณะที่ไม่มีตัวแปรสองตัวใดเท่ากันหรือไม่เท่ากันเสมอในทุกคำตอบ จากนั้นพื้นที่ของการกำหนดค่าความจริงทั้งหมดให้กับตัวแปรของอินสแตนซ์นี้จะก่อตัวเป็นไฮเปอร์คิวบ์ สำหรับแต่ละข้อความที่สร้างขึ้นเป็นการเชื่อมแบบเลือกของตัวแปรสองตัวหรือส่วนเติมเต็มของตัวแปรเหล่านั้นในอินสแตนซ์ 2-satisfiability สามารถสร้างการหดตัวของไฮเปอร์คิวบ์ซึ่งการกำหนดค่าความจริงที่ละเมิดข้อความนี้จะถูกแมปไปยังการกำหนดค่าความจริงซึ่งตัวแปรทั้งสองตรงตามข้อความโดยไม่เปลี่ยนแปลงตัวแปรอื่นในการกำหนดค่าความจริง การประกอบกันของการหดตัวที่เกิดขึ้นในลักษณะนี้สำหรับแต่ละข้อความย่อย จะทำให้เกิดการหดตัวของไฮเปอร์คิวบ์ไปยังปริภูมิคำตอบของอินสแตนซ์ และด้วยเหตุนี้จึงให้การแสดงแทนเป็นการหดตัวของไฮเปอร์คิวบ์ โดยเฉพาะอย่างยิ่ง กราฟมัธยฐานเป็นกราฟย่อยแบบไอโซเมตริกของไฮเปอร์คิวบ์ และด้วยเหตุนี้จึงเป็นคิวบ์บางส่วนอย่างไรก็ตาม ไม่ใช่ว่าคิวบ์บางส่วนทั้งหมดจะเป็นกราฟมัธยฐาน ตัวอย่างเช่นกราฟวงจร หกจุดยอด เป็นคิวบ์บางส่วน แต่ไม่ใช่กราฟมัธยฐาน ${\displaystyle G}$${\displaystyle G}$

ตามที่Imrich & Klavžar (2000)อธิบายไว้ การฝังแบบไอโซเมตริกของกราฟมัธยฐานลงในไฮเปอร์คิวบ์สามารถสร้างได้ในเวลาโดยที่และคือจำนวนจุดยอดและขอบของกราฟตามลำดับ^{[ 21 ]}${\displaystyle O(m\log n)}$${\displaystyle n}$${\displaystyle m}$

ปัญหาของการทดสอบว่ากราฟเป็นกราฟมัธยฐานหรือไม่ และกราฟปราศจากสามเหลี่ยมหรือไม่ ต่างก็ได้รับการศึกษามาเป็นอย่างดีเมื่อImrich, Klavžar & Mulder (1999)สังเกตว่าในแง่หนึ่ง การคำนวณนั้นเทียบเท่ากัน^{[ 22 ]}ดังนั้น ขอบเขตเวลาที่ดีที่สุดที่ทราบสำหรับการทดสอบว่ากราฟปราศจากสามเหลี่ยมหรือไม่[ ^{23 ] จึง}ใช้ได้กับการทดสอบว่ากราฟเป็นกราฟมัธยฐานหรือไม่ และการปรับปรุงใดๆ ในอัลกอริธึมการทดสอบกราฟมัธยฐานก็จะนำไปสู่การปรับปรุงอัลกอริธึมสำหรับการตรวจจับสามเหลี่ยมในกราฟด้วย ${\displaystyle O(m^{1.41})}$

ในทิศทางหนึ่ง สมมติว่าเราได้รับกราฟ เป็นอินพุตและต้องทดสอบว่าเป็นกราฟที่ไม่มีสามเหลี่ยมหรือไม่ จากสร้างกราฟใหม่ที่มีจุดยอดเป็นเซตของจุดยอดที่อยู่ติดกันศูนย์ หนึ่ง หรือสองจุดของ เซตสองเซตดังกล่าวจะอยู่ติดกันในเมื่อจุดยอดทั้งสองแตกต่างกันเพียงหนึ่งจุดเท่านั้น คำอธิบายที่เทียบเท่าของ คือ กราฟนี้ เกิดจากการแยกขอบแต่ละด้านของออกเป็นเส้นทางสองขอบ และเพิ่มจุดยอดใหม่ที่เชื่อมต่อกับจุดยอดเดิมทั้งหมดของกราฟนี้เป็นคิวบ์บางส่วนโดยการสร้าง แต่จะเป็นกราฟมัธยฐานก็ต่อเมื่อเป็นกราฟที่ไม่มีสามเหลี่ยมเท่านั้น: ถ้า, , และสร้างสามเหลี่ยมในแล้ว, , และไม่มีมัธยฐานในเพราะมัธยฐานดังกล่าวจะต้องสอดคล้องกับเซตแต่เซตของจุดยอดสามจุดขึ้นไปของจะไม่สร้างจุดยอดในดังนั้นจะไม่มีสามเหลี่ยมก็ต่อเมื่อเป็นกราฟมัธยฐาน ในกรณีที่ไม่มีสามเหลี่ยมคือกราฟซิมเพล็กซ์ ของ มัน ด้วยโครงสร้างนี้ อัลกอริทึมที่ใช้ทดสอบได้อย่างมีประสิทธิภาพว่ากราฟนั้นเป็นกราฟมัธยฐานหรือไม่ ก็สามารถนำไปใช้ทดสอบได้ว่ากราฟนั้นปราศจากสามเหลี่ยมหรือไม่ การแปลงนี้ช่วยรักษาความซับซ้อนในการคำนวณของปัญหาไว้ได้ เนื่องจากขนาดของกราฟนั้นเป็นสัดส่วนกับขนาดของกราฟ ${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$${\displaystyle H}$${\displaystyle H}$${\displaystyle G}$${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle G}$${\displaystyle \{a,b\}}$${\displaystyle \{a,c\}}$${\displaystyle \{b,c\}}$${\displaystyle H}$${\displaystyle \{a,b,c\}}$${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$${\displaystyle H}$${\displaystyle H}$${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$

การลดรูปในทิศทางตรงกันข้าม จากการตรวจจับสามเหลี่ยมไปสู่การทดสอบกราฟมัธยฐานนั้นซับซ้อนกว่าและขึ้นอยู่กับอัลกอริทึมการจดจำกราฟมัธยฐานก่อนหน้านี้ของHagauer, Imrich & Klavžar (1999)ซึ่งทดสอบเงื่อนไขที่จำเป็นหลายประการสำหรับกราฟมัธยฐานในเวลาเกือบเชิงเส้น ขั้นตอนใหม่ที่สำคัญเกี่ยวข้องกับการใช้การค้นหาแบบกว้าง (breadth first search) เพื่อแบ่งจุดยอดของกราฟออกเป็นระดับตามระยะห่างจากจุดยอดรากที่เลือกไว้โดยพลการ สร้างกราฟจากแต่ละระดับซึ่งจุดยอดสองจุดจะอยู่ติดกันหากมีจุดยอดข้างเคียงร่วมกันในระดับก่อนหน้า และค้นหาสามเหลี่ยมในกราฟเหล่านี้ ค่ามัธยฐานของสามเหลี่ยมดังกล่าวจะต้องเป็นจุดยอดข้างเคียงร่วมกันของจุดยอดทั้งสามของสามเหลี่ยม หากไม่มีจุดยอดข้างเคียงร่วมกัน กราฟนั้นจะไม่ใช่กราฟมัธยฐาน หากสามเหลี่ยมทั้งหมดที่พบในวิธีนี้มีค่ามัธยฐาน และอัลกอริทึมก่อนหน้านี้พบว่ากราฟนั้นตรงตามเงื่อนไขอื่นๆ ทั้งหมดสำหรับการเป็นกราฟมัธยฐาน แสดงว่ากราฟนั้นเป็นกราฟมัธยฐานจริงๆ อัลกอริทึมนี้ไม่เพียงแต่ต้องการความสามารถในการตรวจสอบว่ามีสามเหลี่ยมอยู่หรือไม่ แต่ยังต้องการรายการของสามเหลี่ยมทั้งหมดในกราฟระดับด้วย ในกราฟใดๆ การแสดงรายการสามเหลี่ยมทั้งหมดบางครั้งอาจต้องใช้เวลา เนื่องจากกราฟบางกราฟมีสามเหลี่ยมจำนวนมาก อย่างไรก็ตาม Hagauer และคณะได้แสดงให้เห็นว่าจำนวนสามเหลี่ยมที่เกิดขึ้นในกราฟระดับของการลดรูปนั้นใกล้เคียงกับเชิงเส้น ทำให้สามารถใช้เทคนิคการคูณเมทริกซ์อย่างรวดเร็วของ Alon และคณะในการค้นหาสามเหลี่ยมได้ ${\displaystyle \Omega (m^{3/2})}$

แผนภูมิวิวัฒนาการ (Phylogeny)คือการอนุมานแผนภูมิวิวัฒนาการจากลักษณะที่สังเกตได้ของสิ่งมีชีวิตแผนภูมิดังกล่าวต้องวางสิ่งมีชีวิตไว้ที่จุดยอดที่แตกต่างกัน และอาจมีจุดยอดแฝง เพิ่มเติม แต่จุดยอดแฝงเหล่านั้นต้องมีขอบเชื่อมต่ออย่างน้อยสามขอบขึ้นไป และต้องระบุลักษณะเฉพาะด้วย ลักษณะเฉพาะจะเป็นแบบไบนารีเมื่อมีค่าที่เป็นไปได้เพียงสองค่า และชุดของสิ่งมีชีวิตและลักษณะเฉพาะของพวกมันจะแสดงแผนภูมิวิวัฒนาการที่สมบูรณ์แบบเมื่อมีแผนภูมิวิวัฒนาการที่จุดยอด (สิ่งมีชีวิตและจุดยอดแฝง) ที่ระบุด้วยค่าลักษณะเฉพาะใดๆ ก็ตามก่อตัวเป็นแผนภูมิย่อยที่ต่อเนื่องกัน หากไม่สามารถสร้างแผนภูมิที่มีแผนภูมิวิวัฒนาการที่สมบูรณ์แบบได้ มักเป็นที่ต้องการที่จะหาแผนภูมิที่แสดงความประหยัดสูงสุดหรือเทียบเท่ากับการลดจำนวนครั้งที่จุดปลายของขอบแผนภูมิมีค่าที่แตกต่างกันสำหรับลักษณะเฉพาะอย่างใดอย่างหนึ่ง โดยรวมค่าทั้งหมดจากทุกขอบและทุกลักษณะเฉพาะ

Buneman (1971)อธิบายวิธีการอนุมานแผนภูมิวิวัฒนาการที่สมบูรณ์แบบสำหรับลักษณะไบนารี เมื่อมีอยู่ วิธีการของเขาสามารถขยายไปสู่การสร้างกราฟมัธยฐานสำหรับชุดของสปีชีส์และลักษณะไบนารีใดๆ ได้อย่างเป็นธรรมชาติ ซึ่งเรียกว่าเครือข่ายมัธยฐานหรือกราฟ Buneman ^{[ 24 ]} และเป็น เครือข่ายวิวัฒนาการประเภทหนึ่งต้นไม้วิวัฒนาการแบบประหยัดสูงสุดทุกต้นจะฝังตัวอยู่ในกราฟ Buneman ในแง่ที่ว่าขอบของต้นไม้จะตามเส้นทางในกราฟ และจำนวนการเปลี่ยนแปลงค่าลักษณะบนขอบของต้นไม้จะเท่ากับจำนวนในเส้นทางที่สอดคล้องกัน กราฟ Buneman จะเป็นต้นไม้ก็ต่อเมื่อมีแผนภูมิวิวัฒนาการที่สมบูรณ์แบบอยู่ ซึ่งเกิดขึ้นเมื่อไม่มีลักษณะที่ไม่เข้ากันสองลักษณะใดที่สังเกตเห็นการรวมกันของค่าลักษณะทั้งสี่แบบ

ในการสร้างกราฟ Buneman สำหรับชุดของสายพันธุ์และลักษณะเฉพาะ ขั้นแรก ให้กำจัดสายพันธุ์ที่ซ้ำซ้อนซึ่งไม่สามารถแยกแยะได้จากสายพันธุ์อื่น และลักษณะเฉพาะที่ซ้ำซ้อนซึ่งเหมือนกับลักษณะเฉพาะอื่นเสมอ จากนั้น สร้างจุดยอดแฝงสำหรับทุกชุดค่าลักษณะเฉพาะ โดยที่ค่าลักษณะเฉพาะสองค่าใดๆ ก็ตามมีอยู่ในสายพันธุ์ที่รู้จักอยู่แล้ว ในตัวอย่างที่แสดง มีหนูตัวเล็กสีน้ำตาลไม่มีหาง หนูตัวเล็กสีเงินไม่มีหาง หนูตัวเล็กสีน้ำตาลมีหาง หนูตัวใหญ่สีน้ำตาลมีหาง และหนูตัวใหญ่สีเงินมีหาง วิธีการสร้างกราฟ Buneman จะสร้างจุดยอดแฝงที่สอดคล้องกับสายพันธุ์ที่ไม่รู้จักของหนูตัวเล็กสีเงินมีหาง เนื่องจากทุกคู่ค่า (เล็กและสีเงิน เล็กและมีหาง และสีเงินและมีหาง) พบได้ในสายพันธุ์อื่นๆ ที่รู้จักอยู่แล้ว อย่างไรก็ตาม วิธีนี้จะไม่สามารถอนุมานการมีอยู่ของหนูตัวใหญ่สีน้ำตาลไม่มีหางได้ เพราะยังไม่มีหนูตัวใดที่ทราบว่ามีทั้งลักษณะใหญ่และไม่มีหาง เมื่อกำหนดจุดยอดแฝงแล้ว ให้สร้างขอบระหว่างทุกคู่ของสายพันธุ์หรือจุดยอดแฝงที่แตกต่างกันในลักษณะเฉพาะเพียงอย่างเดียว

เราสามารถอธิบายชุดลักษณะไบนารีได้เทียบเท่ากับระบบแยกซึ่ง เป็น ตระกูลของเซตที่มีคุณสมบัติว่าเซตส่วนเติมเต็มของแต่ละเซตในตระกูลก็อยู่ในตระกูลด้วย ระบบแยกนี้มีเซตสำหรับแต่ละค่าลักษณะ ซึ่งประกอบด้วยชนิดที่มีค่านั้น เมื่อรวมจุดยอดแฝงเข้าไป ระบบแยกที่ได้จะมีคุณสมบัติ Helly กล่าว คือ ตระกูลย่อยที่ตัดกันเป็นคู่ๆ ทุกคู่จะมีจุดตัดร่วมกัน ในบางแง่ กราฟมัธยฐานมีลักษณะเฉพาะที่มาจากระบบแยก Helly: คู่ ที่กำหนดสำหรับแต่ละขอบuvของกราฟมัธยฐานก่อให้เกิดระบบแยก Helly ดังนั้นหากนำการสร้างกราฟ Buneman มาใช้กับระบบนี้ จะไม่จำเป็นต้องมีจุดยอดแฝง และผลลัพธ์จะเหมือนกับกราฟเริ่มต้น^{[ 25 ]}${\displaystyle (W_{uv},\,W_{vu})}$

Bandelt et al. (1995)และBandelt, Macaulay & Richards (2000)อธิบายเทคนิคสำหรับการคำนวณกราฟ Buneman ด้วยมือแบบง่าย และใช้การสร้างนี้เพื่อแสดงภาพความสัมพันธ์ทางพันธุกรรมของมนุษย์

• ผลคูณคาร์ทีเซียนของกราฟค่ามัธยฐานสองกราฟใดๆ ก็ตาม จะได้กราฟค่ามัธยฐานอีกกราฟหนึ่ง ค่ามัธยฐานในกราฟผลคูณสามารถคำนวณได้โดยการหาค่ามัธยฐานในสองปัจจัยนั้นโดยอิสระ เช่นเดียวกับค่ามัธยฐานในกราฟตารางที่สามารถคำนวณได้โดยการหาค่ามัธยฐานในแต่ละมิติเชิงเส้นโดยอิสระ
• ค่าwindexของกราฟวัดปริมาณการมองล่วงหน้าที่จำเป็นในการแก้ปัญหาอย่างเหมาะสม โดยที่กำหนดให้ลำดับของจุดยอดกราฟและต้องหาผลลัพธ์เป็นลำดับของจุดยอดอีกชุดหนึ่งที่ลดผลรวมของระยะทางd ( , )และd ( , ) ให้เหลือ น้อยที่สุด กราฟมัธยฐานคือกราฟที่มีค่า windex เท่ากับ 2 ในกราฟมัธยฐาน ตัวเลือกที่เหมาะสมที่สุดคือการตั้งค่า^{[ 1 ]}${\displaystyle s_{i}}$${\displaystyle t_{i}}$${\displaystyle s_{i}}$${\displaystyle t_{i}}$${\displaystyle t_{i-1}}$${\displaystyle t_{i}}$${\displaystyle t_{i}=m(t_{i-1},s_{i},s_{i+1})}$
• คุณสมบัติของการมีจุดมัธยฐานที่ไม่ซ้ำกันเรียกว่าคุณสมบัติจุดสไตเนอร์ที่ไม่ซ้ำกัน^{[ 1 ]}ต้นไม้สไตเนอร์ที่เหมาะสมที่สุดสำหรับจุดยอดสามจุด, , และในกราฟมัธยฐานสามารถพบได้จากการรวมกันของเส้นทางที่สั้นที่สุดสามเส้นทาง จาก, , และไปยังBandelt & Barthélémy (1984)ศึกษาปัญหาการหาจุดยอดที่ลดผลรวมของระยะทางไปยังแต่ละจุดยอดในชุดที่กำหนด และแสดงให้เห็นว่ามีคำตอบที่ไม่ซ้ำกันสำหรับจำนวนจุดยอดคี่ใดๆ ในกราฟมัธยฐาน พวกเขายังแสดงให้เห็นว่ามัธยฐานของชุดจุดยอดในกราฟมัธยฐานนี้เป็นไปตามเกณฑ์ Condorcetสำหรับผู้ชนะการเลือกตั้งกล่าวคือ เมื่อเปรียบเทียบกับจุดยอดอื่นๆ มันจะอยู่ใกล้กับจุดยอดส่วนใหญ่ใน${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle m(a,b,c)}$${\displaystyle S}$${\displaystyle S}$
• เช่นเดียวกับลูกบาศก์บางส่วนโดยทั่วไป กราฟมัธยฐานทุกกราฟที่มีจุดยอดจะมีขอบไม่เกินอย่างไรก็ตาม จำนวนขอบต้องไม่น้อยเกินไป: Klavžar, Mulder & Škrekovski (1998)พิสูจน์ว่าในกราฟมัธยฐานทุกกราฟ อสมการนี้เป็นจริง โดยที่คือจำนวนขอบ และคือมิติของไฮเปอร์คิวบ์ที่กราฟเป็นรีแทร็กต์ อสมการนี้จะเป็นสมการก็ต่อเมื่อกราฟมัธยฐานไม่มีลูกบาศก์ นี่เป็นผลมาจากเอกลักษณ์อีกอย่างหนึ่งสำหรับกราฟมัธยฐาน: ลักษณะเฉพาะของออยเลอร์จะเท่ากับหนึ่งเสมอ โดยผลรวมจะคำนวณจากกราฟย่อยไฮเปอร์คิวบ์ทั้งหมดของกราฟมัธยฐานที่กำหนด^{[ 26 ]}${\displaystyle n}$${\displaystyle (n/2)\log _{2}n}$${\displaystyle 2n-m-k\leq 2}$${\displaystyle m}$${\displaystyle k}$${\displaystyle \sum (-1)^{\dim(Q)}}$${\displaystyle Q}$
• กราฟมัธยฐานปกติเพียงอย่างเดียว คือไฮเปอร์คิวบ์ ^{[ 27 ]}
• กราฟมัธยฐานทุกกราฟเป็นกราฟโมดูลาร์กราฟโมดูลาร์เป็นกลุ่มของกราฟที่จุดยอดสามจุดทุกจุดมีมัธยฐาน แต่ไม่จำเป็นต้องเป็นมัธยฐานที่ไม่ซ้ำกัน^{[ 28 ]}

• กราฟค่ามัธยฐานระบบสารสนเทศสำหรับการจัดกลุ่มคลาสกราฟ
• Networkคือซอฟต์แวร์สร้างแผนผังวิวัฒนาการแบบฟรี Network สร้างแผนผังและเครือข่ายวิวัฒนาการจากข้อมูลทางพันธุกรรม ภาษาศาสตร์ และข้อมูลอื่นๆ
• PhyloMurkaซอฟต์แวร์โอเพนซอร์สสำหรับการคำนวณเครือข่ายค่ามัธยฐานจากข้อมูลทางชีววิทยา