ในคณิตศาสตร์ของความแข็งแกร่งเชิงโครงสร้างเมทริกซ์ความแข็งแกร่ง (rigidity matroid)คือเมทริกซ์ที่อธิบายจำนวนองศาอิสระของกราฟแบบไม่มีทิศทางที่มีขอบแข็งที่มีความยาวคงที่ ซึ่งฝังอยู่ในปริภูมิยุคลิดในเมทริกซ์ความแข็งแกร่งสำหรับกราฟที่มีnจุดยอดใน ปริภูมิ dมิติ เซตของขอบที่กำหนดกราฟย่อยที่มีkองศาอิสระจะมีอันดับเมทริกซ์เท่ากับ dn  −  kเซตของขอบจะเป็นอิสระก็ต่อเมื่อ สำหรับทุกขอบในเซต การลบขอบนั้นจะเพิ่มจำนวนองศาอิสระของกราฟย่อยที่เหลืออยู่^{[ 1 ] [ 2 ] [ 3 ]}

เฟรมเวิร์กคือกราฟแบบไม่มีทิศทางที่ฝังอยู่ใน ปริภูมิยุคลิดมิติ dโดยการให้ พิกัด คาร์ทีเซียนdชุดสำหรับแต่ละจุดยอดของกราฟ จากเฟรมเวิร์กที่มี จุดยอด nจุดและ ขอบ mเส้น เราสามารถกำหนดเมทริกซ์ที่มีmแถวและndคอลัมน์ ซึ่งเป็นเวอร์ชันขยายของเมทริกซ์เหตุการณ์ของกราฟที่เรียกว่าเมทริกซ์ความแข็งแกร่งในเมทริกซ์นี้ ค่าในแถวeและคอลัมน์ ( v , i ) จะเป็นศูนย์หากvไม่ใช่จุดปลายของขอบeในทางกลับกัน หากขอบeมีจุดยอดuและvเป็นจุดปลาย ค่าของค่าในแถว e จะเป็นผลต่างระหว่างพิกัด ที่ iของvและu ^{[ 1 ] [ 3 ]}

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

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

ปริภูมิเวกเตอร์ของภาระที่เป็นไปได้ทั้งหมดบนระบบที่มี จุดยอด nจุด มีมิติdnซึ่งภาระสมดุลจะก่อตัวเป็นปริภูมิย่อยที่มีมิติ เซตอิสระในเมทริกซ์ความแข็งแกร่งมีระบบของภาระสมดุลที่มีมิติเท่ากับจำนวนสมาชิกของเซต ดังนั้นอันดับสูงสุดที่เซตใด ๆ ในเมทริกซ์ความแข็งแกร่งสามารถมีได้คือถ้าเซตมีอันดับนี้ เซตของความเค้นของเซตนั้นจะเหมือนกับปริภูมิของภาระสมดุล หรืออีกนัยหนึ่งและเทียบเท่ากัน ในกรณีนี้ ภาระสมดุลทุกตัวบนโครงสร้างอาจได้รับการแก้ไขโดยความเค้นที่สร้างชุดของแรงที่เท่ากันและตรงข้ามกัน และโครงสร้างนั้นกล่าวได้ว่ามีความแข็งแกร่งทางสถิต^{[ 3 ]}${\displaystyle dn-{\binom {d+1}{2}}}$${\displaystyle dn-{\binom {d+1}{2}}}$

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

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

การเคลื่อนที่แบบแข็งเกร็งของเฟรมเวิร์กคือการเคลื่อนที่ที่ทำให้เฟรมเวิร์กมีความสอดคล้องกับการกำหนดค่าเดิม ณ จุดเวลาแต่ละจุด การเคลื่อนที่แบบแข็งเกร็งรวมถึงการเลื่อนและการหมุนในปริภูมิยุคลิด เกรเดียนต์ของการเคลื่อนที่แบบแข็งเกร็งก่อให้เกิดปริภูมิเชิงเส้นที่มีการเลื่อนและการหมุนเป็นฐาน ซึ่งมีมิติเท่ากับซึ่งจะต้องเป็นปริภูมิย่อยของปริภูมิว่างของเมทริกซ์ความแข็งเกร็งเสมอ เนื่องจากปริภูมิว่างมีมิติอย่างน้อยเท่ากับมิตินี้เสมอ เมทริกซ์ความแข็งเกร็งจึงมีอันดับได้มากที่สุดเท่ากับและเมื่อมีอันดับนี้ การเคลื่อนที่เพียงอย่างเดียวที่รักษาระยะความยาวของขอบของเฟรมเวิร์กคือการเคลื่อนที่แบบแข็งเกร็ง ในกรณีนี้ เฟรมเวิร์กจะเรียกว่าแข็งเกร็งอันดับหนึ่ง (หรือแข็งเกร็งแบบอนันต์) ^{[ 1 ] [ 3 ]}โดยทั่วไป ขอบจะเป็นส่วนหนึ่งของการดำเนินการปิดเมทริกซ์ของเซตก็ต่อเมื่อไม่มีการเคลื่อนที่ต่อเนื่องของเฟรมเวิร์กที่เปลี่ยนแปลงความยาวของเซตแต่ยังคงความยาวของขอบในเซตไว้ไม่เปลี่ยนแปลง^{[ 1 ]}${\displaystyle {\binom {d+1}{2}}}$${\displaystyle dn-{\binom {d+1}{2}}}$${\displaystyle e}$${\displaystyle S}$${\displaystyle e}$${\displaystyle S}$

แม้ว่าจะกำหนดด้วยเงื่อนไขที่แตกต่างกัน (เวกเตอร์คอลัมน์เทียบกับเวกเตอร์แถว หรือแรงเทียบกับการเคลื่อนที่) ความแข็งแกร่งแบบสถิตและความแข็งแกร่งลำดับแรกจะลดลงเหลือคุณสมบัติเดียวกันของเมทริกซ์พื้นฐานและจึงตรงกัน ในสองมิติ เมทริกซ์ความแข็งแกร่งทั่วไปยังอธิบายจำนวนองศาอิสระของการเคลื่อนที่ประเภทอื่น ซึ่งขอบแต่ละด้านถูกจำกัดให้ขนานกับตำแหน่งเดิมแทนที่จะถูกจำกัดให้มีความยาวเท่าเดิม อย่างไรก็ตาม ความเท่าเทียมกันระหว่างความแข็งแกร่งและการเคลื่อนที่แบบขนานจะพังทลายลงในมิติที่สูงกว่า^{[ 3 ]}

กรอบงานจะมีรูปแบบการรับรู้ที่ไม่ซ้ำกันใน พื้นที่ dมิติ หากการวางกราฟเดียวกันที่มีความยาวขอบเท่ากันทุกตำแหน่งจะสอดคล้องกับกรอบงานนั้น กรอบงานดังกล่าวจะต้องมีความแข็งแกร่ง เพราะมิฉะนั้นจะมีการเคลื่อนที่อย่างต่อเนื่องที่นำไปสู่ตำแหน่งที่ไม่สอดคล้องกับความยาวขอบเท่ากัน แต่ความสามารถในการรับรู้ที่ไม่ซ้ำกันนั้นแข็งแกร่งกว่าความแข็งแกร่ง ตัวอย่างเช่นกราฟรูปเพชร (สามเหลี่ยมสองรูปที่ใช้ขอบร่วมกัน) มีความแข็งแกร่งในสองมิติ แต่ไม่สามารถรับรู้ได้ที่ไม่ซ้ำกัน เนื่องจากมีรูปแบบการรับรู้ที่แตกต่างกันสองแบบ แบบหนึ่งที่สามเหลี่ยมอยู่ด้านตรงข้ามของขอบร่วมกัน และอีกแบบหนึ่งที่สามเหลี่ยมทั้งสองอยู่ด้านเดียวกัน กราฟที่สามารถรับรู้ได้ที่ไม่ซ้ำกันมีความสำคัญในแอปพลิเคชันที่เกี่ยวข้องกับการสร้างรูปร่างขึ้นใหม่จากระยะทาง เช่นการหาตำแหน่งโดยใช้สามเหลี่ยมในการสำรวจที่ดิน^{[ 4 ]}การกำหนดตำแหน่งของโหนดในเครือข่ายเซ็นเซอร์ไร้สาย [ ^{5 ]}และการสร้างโครงสร้างของโมเลกุลขึ้นใหม่ผ่าน สเปกโทรสโก ^ปีเรโซแนนซ์แม่เหล็กนิวเคลียร์^{[ 4 ]}

Bruce Hendrickson นิยามกราฟว่ามีความแข็งตัวเกินความจำเป็น (redundantly rigid)หากกราฟนั้นยังคงแข็งตัวอยู่หลังจากลบขอบใดขอบหนึ่งออกไป ในแง่ของ matroid หมายความว่า matroid ความแข็งตัวนั้นมีอันดับเต็ม (full rank) และ matroid นั้นไม่มี coloop ใดๆ Hendrickson พิสูจน์ว่าเฟรมเวิร์กที่สามารถสร้างได้เพียงหนึ่งเดียว (uniquely realizable framework) ทุกเฟรมเวิร์ก (ที่มีความยาวขอบทั่วไป) นั้นเป็นกราฟสมบูรณ์ (complete graph ) หรือ กราฟที่เชื่อมต่อจุดยอดและแข็งตัวเกินความจำเป็น ( vertex-connected , redundantly rigid graph) และเขาสันนิษฐานว่านี่คือลักษณะเฉพาะที่แน่นอนของเฟรมเวิร์กที่สามารถสร้างได้เพียง หนึ่งเดียว ^{[ 6 ]}ข้อสันนิษฐานนี้เป็นจริงสำหรับมิติหนึ่งและสองมิติ ตัวอย่างเช่น ในกรณีหนึ่งมิติ กราฟจะสามารถสร้างได้เพียงหนึ่งเดียวก็ต่อเมื่อมันเชื่อมต่อกันและไม่มีสะพาน^{[ 7 ]}อย่างไรก็ตาม ข้อสันนิษฐานของ Hendrickson เป็นเท็จสำหรับสามมิติขึ้นไป^{[ 8 ]}สำหรับเฟรมเวิร์กที่ไม่ใช่แบบทั่วไป การพิจารณาว่าเฟรมเวิร์กที่กำหนดนั้นสามารถสร้างได้เพียงหนึ่งเดียวหรือไม่นั้นเป็นปัญหา NP-hard ^{[ 9 ]}${\displaystyle dn-{\binom {d+1}{2}}}$${\displaystyle (d+1)}$

Streinu & Theran (2009)นิยามกราฟว่าเป็น-sparse ถ้ากราฟย่อยที่ไม่ว่างเปล่าทุกกราฟที่มีจุดยอดมีขอบไม่เกินและ-tight ถ้าเป็น-sparse และมีขอบ พอดี ^{[ 10 ]}จากการพิจารณาภาระและความเครียด จะเห็นได้ว่าเซตของขอบที่เป็นอิสระในเมทริกซ์ความแข็งแกร่งก่อให้เกิดกราฟ -sparse เพราะถ้าไม่เช่นนั้นจะมีกราฟย่อยที่มีจำนวนขอบเกินมิติของพื้นที่ของภาระสมดุล ซึ่งส่งผลให้มีความเครียดในตัวเอง ด้วยเหตุผลที่คล้ายกัน เซตของขอบที่เป็นทั้งอิสระและแข็งแกร่งก่อให้เกิดกราฟ -tight ตัวอย่างเช่น ในมิติเดียว เซตอิสระก่อให้เกิดเซตขอบของป่า กราฟ (1,1)-sparse และเซตแข็งแกร่งอิสระก่อให้เกิดเซตขอบของต้นไม้ กราฟ (1,1)-tight ในกรณีนี้ เมทริกซ์ความแข็งแกร่งของเฟรมเวิร์กจะเหมือนกับเมทริกซ์กราฟิกของกราฟที่สอดคล้องกัน^{[ 2 ]}${\displaystyle (k,l)}$${\displaystyle n}$${\displaystyle kn-l}$${\displaystyle (k,l)}$${\displaystyle (k,l)}$${\displaystyle kn-l}$${\displaystyle (d,{\binom {d+1}{2}})}$${\displaystyle (d,{\binom {d+1}{2}})}$

ในสองมิติLaman (1970)แสดงให้เห็นว่าลักษณะเดียวกันนี้เป็นจริง: เซตอิสระก่อตัวเป็นเซตขอบของกราฟแบบเบาบาง (2,3) และเซตแข็งอิสระก่อตัวเป็นเซตขอบของกราฟแบบแน่น (2,3) ^{[ 11 ]}จากงานนี้ กราฟแบบแน่น (2,3) (กราฟของกรอบงานทั่วไปที่แข็งน้อยที่สุดในสองมิติ) ได้กลายเป็นที่รู้จักในชื่อกราฟ Lamanตระกูลของกราฟ Laman บนเซตของจุดยอดที่กำหนดไว้จะก่อตัวเป็นเซตของฐานของเมทริกซ์ความแข็งของกราฟสมบูรณ์และโดยทั่วไปแล้วสำหรับทุกกราฟที่ก่อตัวเป็นกรอบงานแข็งในสองมิติ กราฟย่อย Laman ที่ครอบคลุมของจะเป็นฐานของเมทริกซ์ความแข็งของ ${\displaystyle n}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$

อย่างไรก็ตาม ในมิติที่สูงกว่านั้นกราฟที่แน่นบางกราฟไม่ได้มีความแข็งตัวน้อยที่สุดเสมอไป และการกำหนดลักษณะของกราฟที่แข็งตัวน้อยที่สุด (ฐานของเมทริกซ์ความแข็งตัวของกราฟสมบูรณ์) เป็นปัญหาเปิดที่สำคัญ^{[ 12 ]}${\displaystyle (d,{\binom {d+1}{2}})}$