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

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

กราฟบล็อกอาจมีลักษณะเป็นกราฟจุดตัดของบล็อกของกราฟที่ไม่มีทิศทางใดๆ^{[ 4 ]}

กราฟบล็อกคือกราฟที่สำหรับจุดยอดทั้งสี่u , v , xและyระยะทางสองค่าที่มากที่สุดจากระยะทางสามค่าd ( u , v ) + d ( x , y ) , d ( u , x ) + d ( v , y )และd ( u , y ) + d ( v , x )จะเท่ากันเสมอ^{[ 2 ] [ 5 ]}

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

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

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

ต้นไม้ทุกต้นกราฟคลัสเตอร์หรือกราฟกังหันลม ล้วนเป็นกราฟบล็อกทั้งสิ้น

กราฟบล็อกทุกอันมีค่า boxicityไม่เกินสอง^{[ 7 ]}

กราฟบล็อกเป็นตัวอย่างของกราฟค่ามัธยฐาน เทียม : สำหรับจุดยอดทั้งสามจุด จะมีจุดยอดที่ไม่ซ้ำกันเพียงจุดเดียวที่อยู่ในเส้นทางที่สั้นที่สุดระหว่างจุดยอดทั้งสามจุด หรือมีสามเหลี่ยมที่ไม่ซ้ำกันเพียงรูปเดียวที่มีขอบอยู่บนเส้นทางที่สั้นที่สุดทั้งสามเส้นนี้^{[ 7 ]}

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

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

ถ้าGเป็นกราฟแบบไม่มีทิศทางใดๆ บล็อกกราฟของGซึ่งเขียนแทนด้วยB ( G ) คือกราฟจุดตัดของบล็อกของG : B ( G ) มีจุดยอดสำหรับส่วนประกอบที่เชื่อมต่อกันสองจุดทุกส่วนของGและจุดยอดสองจุดของB ( G ) จะอยู่ติดกันหากบล็อกสองบล็อกที่สอดคล้องกันมาบรรจบกันที่จุดยอดเชื่อมต่อ ถ้า_K1 แทนกราฟที่มีจุดยอดหนึ่งจุด_B ( K1 )จะถูกกำหนดให้เป็นกราฟว่างB ( G ) จำเป็นต้องเป็นบล็อกกราฟ: มันมีส่วนประกอบที่เชื่อมต่อกันสองจุดหนึ่งส่วนสำหรับจุดยอดเชื่อมต่อแต่ละจุดของGและส่วนประกอบที่เชื่อมต่อกันสองจุดที่สร้างขึ้นในลักษณะนี้จะต้องเป็นคลิก ในทางกลับกัน บล็อกกราฟทุกอันเป็นกราฟB ( G ) สำหรับกราฟG บาง กราฟ^{[ 4 ]}ถ้าGเป็นต้นไม้B ( G ) จะตรงกับกราฟเส้นของG

กราฟB ( B ( G )) มีจุดยอดหนึ่งจุดสำหรับแต่ละจุดยอดของข้อต่อของ^Gจุดยอดสองจุดจะอยู่ติดกันในB ( B ( G )) หากจุดยอดทั้งสองอยู่ในบล็อกเดียวกันในG [ ^{4 ]}