ในทฤษฎีกราฟกราฟk -degenerateคือกราฟแบบไม่มีทิศทางที่ทุกกราฟย่อยมีอย่างน้อยหนึ่งจุดยอดที่มีดีกรีไม่เกินk นั่นคือ จุดยอดบางจุดในกราฟย่อยสัมผัสกับขอบของกราฟย่อยนั้นไม่เกิน k ค่าdegeneracyของกราฟคือค่า k ที่น้อยที่สุดที่ทำให้กราฟนั้นเป็นk-degenerate ค่า degeneracy ของกราฟเป็นตัววัดความเบาบางของกราฟ และอยู่ในช่วงค่าคงที่ของตัววัดความเบาบางอื่นๆ เช่น ค่าarboricityของกราฟ ${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$

ความเสื่อมยังเป็นที่รู้จักในชื่อ k -core number [ ^{1 ]} width ^{[ 2 ]}และlinkage [ ³ ] และโดย ^{พื้นฐานแล้ว}เหมือนกับcoloring number ^{[ 4 ]}หรือ Szekeres ^– Wilf number (ตั้งชื่อตามSzekeresและWilf  ( 1968 )) กราฟที่เสื่อม k ยังถูกเรียกว่าk - inductive graphs ^{[ 5 ]}ความเสื่อมของกราฟสามารถคำนวณได้ในเวลาเชิงเส้นโดยอัลกอริทึมที่ลบจุดยอดที่มีดีกรีต่ำสุดซ้ำๆ^{[ 6 ]}ส่วนประกอบที่เชื่อมต่อกันที่เหลืออยู่หลังจากลบจุดยอดที่มีดีกรีน้อยกว่า k ออก (ซ้ำๆ) เรียกว่าk -coreของกราฟ และความเสื่อมของกราฟคือค่าที่มากที่สุดที่ทำให้กราฟมีk-core ${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$

ป่าจำกัดทุก ป่า จะมีจุดยอดโดดเดี่ยว (ไม่เชื่อมต่อกับขอบใดๆ) หรือจุดยอดใบ (เชื่อมต่อกับขอบเพียงหนึ่งเดียว) และกราฟย่อยทุกกราฟของป่าก็เป็นป่าเช่นกัน ดังนั้น ต้นไม้และป่าจึงเป็นกราฟ 1-degenerate และกราฟ 1-degenerate ทุกกราฟก็เป็นป่าด้วย

กราฟระนาบจำกัดทุกกราฟจะมีจุดยอดที่มีดีกรีห้าหรือน้อยกว่า ดังนั้นกราฟระนาบทุกกราฟจึงเป็นกราฟ 5-degenerate และความเสื่อมของกราฟระนาบใดๆ ก็มีค่าไม่เกินห้า ในทำนองเดียวกันกราฟระนาบภายนอก ทุกกราฟ มีความเสื่อมไม่เกินสอง^{[ 7 ]}และเครือข่าย Apollonianมีความเสื่อมสาม

แบบจำลอง Barabási–Albertสำหรับการสร้างเครือข่ายแบบไร้มาตราส่วนแบบสุ่ม^{[ 8 ]}ถูกกำหนดพารามิเตอร์ด้วยตัวเลขโดยที่แต่ละจุดยอดที่เพิ่มเข้าไปในกราฟจะมีจุดยอดที่เพิ่มเข้ามาก่อนหน้านี้ ส่งผลให้กราฟย่อยใดๆ ของเครือข่ายที่เกิดขึ้นในลักษณะนี้จะมีจุดยอดที่มีดีกรีสูงสุด(จุดยอดสุดท้ายในกราฟย่อยที่ถูกเพิ่มเข้าไปในกราฟ) และเครือข่าย Barabási–Albert จะเสื่อมสภาพ โดยอัตโนมัติ${\displaystyle m}$${\displaystyle m}$${\displaystyle m}$${\displaystyle m}$

กราฟปกติทุกกราฟจะมีค่าความเสื่อม เท่ากับค่าสูงสุด อย่างแน่นอนยิ่งไปกว่านั้น ค่าความเสื่อมของกราฟจะเท่ากับค่าสูงสุดของจุดยอดก็ต่อเมื่ออย่างน้อยหนึ่งส่วนประกอบที่เชื่อมต่อกันของกราฟเป็นกราฟปกติที่มีค่าสูงสุดเท่านั้น สำหรับกราฟอื่นๆ ค่าความเสื่อมจะน้อยกว่าค่าสูงสุดอย่างแน่นอน^{[ 9 ]}${\displaystyle k}$${\displaystyle k}$

จำนวนการระบายสีของกราฟถูกกำหนดโดยPaul ErdősและAndrás Hajnalให้เป็นจำนวนน้อยที่สุดที่มีลำดับของจุดยอดซึ่งแต่ละจุดยอดมีเพื่อนบ้านน้อยกว่าจำนวนที่อยู่ก่อนหน้าในลำดับนั้น ควรแยกแยะจำนวนการระบายสีนี้ออกจากจำนวนสีโครมาติกซึ่งเป็นจำนวนสีขั้นต่ำที่จำเป็นในการระบายสีจุดยอดโดยที่ไม่มีจุดยอดที่อยู่ติดกันสองจุดใดมีสีเดียวกัน ลำดับที่ใช้ในการกำหนดจำนวนการระบายสีจะให้ลำดับในการระบายสีจุดยอดซึ่ง อัลกอริทึม การระบายสีแบบโลภจะใช้จำนวนสีไม่เกินจำนวนการระบายสี อย่างไรก็ตาม โดยทั่วไปแล้ว การระบายสีแบบอื่นอาจใช้สีน้อยกว่า^{[ 4 ]}${\displaystyle G}$${\displaystyle \kappa }$${\displaystyle G}$${\displaystyle \kappa }$${\displaystyle G}$${\displaystyle G}$

ต่อมาและโดยอิสระ ความเสื่อมของกราฟGได้รับการกำหนดโดย Don Lick และ Arthur White ว่าเป็นค่าต่ำสุด ที่ทำให้กราฟ ย่อยที่เหนี่ยวนำทุก กราฟ มีจุดยอดที่มีเพื่อนบ้านอย่างน้อยหนึ่งจุด คำจำกัดความจะเหมือนกันหากอนุญาตให้ใช้กราฟย่อยแบบสุ่มแทนกราฟย่อยที่เหนี่ยวนำ เนื่องจากกราฟย่อยที่ไม่เหนี่ยวนำจะมีดีกรีของจุดยอดได้เฉพาะที่น้อยกว่าหรือเท่ากับดีกรีของจุดยอดในกราฟย่อยที่เหนี่ยวนำโดยเซตของจุดยอดเดียวกันเท่านั้น^{[ 10 ]}${\displaystyle k}$${\displaystyle G}$${\displaystyle k}$

แนวคิดสองประการของจำนวนการระบายสีและความเสื่อมนั้นเทียบเท่ากัน กล่าวคือ ในกราฟจำกัดทุกกราฟ ความเสื่อมจะมีค่าน้อยกว่าจำนวนการระบายสีเพียงหนึ่ง^{[ 11 ]}เพราะถ้ากราฟมีการเรียงลำดับด้วยจำนวนการระบายสีแล้ว ในแต่ละกราฟย่อย จุดยอดที่อยู่ใน และเป็นจุดสุดท้ายในการเรียงลำดับจะมี เพื่อนบ้านไม่เกิน ใน ดังนั้น กราฟย่อยทุกกราฟจึงมีจุดยอดที่มีดีกรีต่ำ ในทางกลับกัน ถ้าเป็นกราฟที่เสื่อมแล้ว การเรียงลำดับด้วยจำนวนการระบายสีสามารถหาได้โดยการค้นหาจุดยอด ที่มี เพื่อนบ้านไม่เกิน ซ้ำๆ ลบ ออก จากกราฟ เรียงลำดับจุดยอดที่เหลือ และเพิ่มเข้าไปที่ส่วนท้ายของการเรียงลำดับ ${\displaystyle \kappa }$${\displaystyle H}$${\displaystyle H}$${\displaystyle \kappa -1}$${\displaystyle H}$${\displaystyle H}$${\displaystyle G}$${\displaystyle k}$${\displaystyle k+1}$${\displaystyle v}$${\displaystyle k}$${\displaystyle v}$${\displaystyle v}$

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

-core ของกราฟคือ กราฟย่อยที่เชื่อมต่อกัน มากที่สุดของกราฟซึ่งจุดยอดทั้งหมดมีดีกรีอย่างน้อยหรือกล่าวอีกนัยหนึ่งคือ เป็นส่วนประกอบที่เชื่อมต่อกันของกราฟย่อยของกราฟที่เกิดจากการลบจุดยอดที่มีดีกรีน้อยกว่า ซ้ำๆ กันถ้ามี -core ที่ไม่ว่างเปล่าอยู่ แสดงว่ากราฟ มีค่าความเสื่อมอย่างน้อยและค่าความเสื่อมของกราฟคือค่าที่มากที่สุดที่กราฟมี-core ${\displaystyle k}$${\displaystyle G}$${\displaystyle G}$${\displaystyle k}$${\displaystyle G}$${\displaystyle k}$${\displaystyle k}$${\displaystyle G}$${\displaystyle k}$${\displaystyle G}$${\displaystyle k}$${\displaystyle G}$${\displaystyle k}$

จุดยอดจะมีความเป็นแกนหลักก็ต่อเมื่อมันเป็นส่วนหนึ่งของ แกนหลักแบบ แต่ไม่ใช่แกนหลัก แบบ ใดๆ${\displaystyle u}$${\displaystyle c}$${\displaystyle c}$${\displaystyle (c+1)}$

แนวคิดของแกน a ถูกนำมาใช้เพื่อศึกษาโครงสร้างการจัดกลุ่มของเครือข่ายสังคม^{[ 13 ]}และเพื่ออธิบายวิวัฒนาการของกราฟสุ่ม [ ^{14 ] นอกจาก}นี้ยังถูกนำไปใช้ในชีวสารสนเทศ [ ^{15 ]}การแสดงภาพเครือข่าย^{[ 16 ]}และความยืดหยุ่นของเครือข่ายในระบบนิเวศ^{[ 17 ]}การสำรวจหัวข้อนี้ ซึ่งครอบคลุมแนวคิดหลัก เทคนิคอัลกอริทึมที่สำคัญ รวมถึงโดเมนการใช้งานบางส่วน สามารถพบได้ใน^Malliaros et al. (2019 ) ${\displaystyle k}$

การซึมผ่านแบบบูตสแตรปเป็นกระบวนการสุ่มที่ศึกษาในฐานะแบบจำลองการระบาด^{[ 18 ]}และในฐานะแบบจำลองสำหรับความทนทานต่อข้อผิดพลาดสำหรับการคำนวณแบบกระจาย [ ^{19 ] ประกอบด้วย}การเลือกชุดย่อยแบบสุ่มของเซลล์ที่ใช้งานอยู่จากแลตทิซหรือพื้นที่อื่น ๆ จากนั้นพิจารณาแกนหลักของกราฟย่อยที่เหนี่ยวนำของชุดย่อยนี้^{[ 20 ]}${\displaystyle k}$

Matula & Beck (1983)ได้อธิบายขั้นตอนวิธีในการหาลำดับความเสื่อมของกราฟที่มีเซตของจุดยอดและเซตของขอบโดยใช้เวลาและ พื้นที่เพียงไม่ กี่คำโดยการจัดเก็บจุดยอดไว้ในคิวแบบบัคเก็ต ที่มีดัชนีตามดีกรี และลบจุดยอดที่มีดีกรีน้อยที่สุดออกซ้ำๆ ความเสื่อมจะพิจารณาจากดีกรีสูงสุดของจุดยอดใดๆ ในขณะที่ถูกลบออก ${\displaystyle G=(V,E)}$${\displaystyle V}$${\displaystyle E}$${\displaystyle O(\vert V\vert +\vert E\vert )}$${\displaystyle O(\vert V\vert )}$${\displaystyle k}$

กล่าวโดยละเอียดแล้ว ขั้นตอนวิธีดำเนินการดังนี้:

• เริ่มต้นรายการผลลัพธ์${\displaystyle L}$
• คำนวณหาจำนวนเพื่อนบ้านของแต่ละจุดยอดในกราฟ ซึ่งก็คือ จำนวนเพื่อนบ้านที่ยังไม่ได้อยู่ในกราฟในขั้นต้น จำนวนเหล่านี้จะเป็นเพียงดีกรีของจุดยอดเหล่านั้น${\displaystyle d_{v}}$${\displaystyle v}$${\displaystyle G}$${\displaystyle v}$${\displaystyle L}$
• สร้างอาร์เรย์เริ่มต้นที่มีรายการของจุดยอดที่ยังไม่ได้อยู่ในซึ่ง เป็นไปตามเงื่อนไข นั่นคือ${\displaystyle D}$${\displaystyle D[i]}$${\displaystyle v}$${\displaystyle L}$${\displaystyle d_{v}=i}$${\displaystyle D[i]=\{v\in V\setminus L\mid d_{v}=i\}}$
• กำหนดค่าเริ่มต้นเป็น 0${\displaystyle k}$
• จำนวนครั้ง ที่ทำซ้ำ: ${\displaystyle n}$
  • สแกนเซลล์ในอาร์เรย์จนกว่าจะพบค่าที่ไม่ว่างเปล่า${\displaystyle D[0],D[1],\dots }$${\displaystyle i}$${\displaystyle D[i]}$
  • ตั้งค่าเป็น.${\displaystyle k}$${\displaystyle \max\{k,i\}}$
  • เลือกจุดยอดใดๆจากเพิ่มเข้าไปที่จุดเริ่มต้นของและลบออกจาก${\displaystyle v}$${\displaystyle D[i]}$${\displaystyle v}$${\displaystyle L}$${\displaystyle D[i]}$
  • สำหรับเพื่อนบ้านแต่ละรายที่ยังไม่ได้อยู่ในให้ลบออกจากลบหนึ่งออกจากและเพิ่มไปยังตำแหน่งที่ระบุด้วยค่าที่อัปเดตของ${\displaystyle w}$${\displaystyle v}$${\displaystyle L}$${\displaystyle w}$${\displaystyle D[d_{w}]}$${\displaystyle d_{w}}$${\displaystyle w}$${\displaystyle D[d_{w}]}$${\displaystyle d_{w}}$

เมื่อสิ้นสุดขั้นตอนวิธี จุดยอดใดๆ จะมี เส้นเชื่อมไปยังจุดยอดอื่นๆ ไม่เกิน โดยที่ คือ แกนหลักของซึ่งเป็นส่วนประกอบที่เชื่อมต่อกันของกราฟย่อยที่เกิดจากจุดยอดโดยที่คือจุดยอดแรกที่มีดีกรีในขณะที่ถูกเพิ่มเข้าไปใน ${\displaystyle L[i]}$${\displaystyle k}$${\displaystyle L[1,\ldots ,i-1]}$${\displaystyle \ell }$${\displaystyle G}$${\displaystyle H_{\ell }\subset G}$${\displaystyle L[1,\ldots ,i]}$${\displaystyle i}$${\displaystyle \geq \ell }$${\displaystyle L}$

ถ้ากราฟมีการวางแนวแบบไม่มีวงจรโดยมีดีกรีขาออกเท่ากับแล้วขอบของกราฟนั้นสามารถแบ่งออกเป็นป่า ได้ โดยการเลือกป่าหนึ่งป่าสำหรับแต่ละขอบขาออกของแต่ละโหนด ดังนั้นค่าความเป็นป่าของ กราฟจึงมี ค่าไม่เกินค่าความเสื่อม ในทางกลับกันกราฟที่มีจุดยอด n จุดซึ่งสามารถแบ่งออกเป็นป่าได้จะมีขอบไม่เกิน n ขอบ และดังนั้นจึงมีจุดยอดที่มีดีกรีไม่เกินn – ดังนั้นค่าความเสื่อมจึงน้อยกว่าสองเท่าของค่าความเป็นป่า นอกจากนี้ยังสามารถคำนวณการวางแนวของกราฟที่ลดดีกรีขาออกให้น้อยที่สุดได้ในเวลาพหุนาม แต่ไม่จำเป็นต้องไม่มีวงจร ขอบของกราฟที่มีการวางแนวเช่นนี้สามารถแบ่งออกเป็นป่าเทียมได้ในลักษณะเดียวกันและในทางกลับกัน การแบ่งขอบของกราฟออกเป็นป่าเทียมใดๆ จะนำไปสู่การวางแนวที่มีดีกรีขาออกเท่ากับ -1 (โดยการเลือกการวางแนวที่มีดีกรีขาออกเท่ากับ 1 สำหรับแต่ละป่าเทียม) ดังนั้นดีกรีขาออกต่ำสุดของการวางแนวเช่นนี้คือค่าความเป็นป่าเทียมซึ่งมีค่าไม่เกินค่าความเสื่อมอีกครั้ง^{[ 21 ]}ความหนายังอยู่ในช่วงค่าคงที่ของความเป็นต้นไม้ และด้วยเหตุนี้จึงอยู่ในช่วงความเสื่อมด้วย^{[ 22 ]}${\displaystyle G}$${\displaystyle k}$${\displaystyle k}$${\displaystyle G}$${\displaystyle n}$${\displaystyle k}$${\displaystyle k(n-1)}$${\displaystyle 2k-1}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$

กราฟที่เสื่อมสภาพแบบ A มีจำนวนสีไม่เกิน; ซึ่งพิสูจน์ได้ด้วยการเหนี่ยวนำอย่างง่ายบนจำนวนจุดยอด ซึ่งเหมือนกับการพิสูจน์ทฤษฎีบทหกสีสำหรับกราฟระนาบทุกประการ เนื่องจากจำนวนสีเป็นขอบเขตบนของลำดับของคลิกสูงสุดตัวแปรคงที่หลังนี้จึงมีค่าความเสื่อมสภาพไม่เกินบวกหนึ่งเช่นกัน โดยใช้ อัลกอริทึม การระบายสีแบบโลภบนลำดับที่มีจำนวนการระบายสีที่เหมาะสมที่สุด เราสามารถระบายสี กราฟที่เสื่อมสภาพแบบ A ได้โดยใช้ สีไม่เกิน^{[ 23 ]}${\displaystyle k}$${\displaystyle k+1}$${\displaystyle k}$${\displaystyle k+1}$

กราฟที่เชื่อมต่อด้วยk จุดยอด คือกราฟที่ไม่สามารถแบ่งออกเป็นส่วนประกอบได้มากกว่าหนึ่งส่วนโดยการลบจุดยอดน้อยกว่าk จุดยอด หรือเทียบเท่ากับกราฟที่จุดยอดแต่ละคู่สามารถเชื่อมต่อกันได้ด้วยเส้นทางที่ไม่มีจุดยอดร่วมกัน เนื่องจากเส้นทางเหล่านี้ต้องออกจากจุดยอดทั้งสองของคู่ผ่านขอบที่ไม่มีจุดยอดร่วมกันกราฟที่เชื่อมต่อด้วย k จุดยอดจึงต้องมีความเสื่อมอย่างน้อย k จุดยอด แนวคิดที่เกี่ยวข้องกับ k-cores แต่ขึ้นอยู่กับการเชื่อมต่อจุดยอด ^ได้รับการศึกษาในทฤษฎีเครือข่ายสังคมภายใต้ชื่อความเชื่อมโยงเชิงโครงสร้าง [ ^{24 ]}${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$

ถ้ากราฟมีtreewidthหรือpathwidthไม่เกินแสดงว่ากราฟนั้นเป็นกราฟย่อยของกราฟคอร์ดัลซึ่งมีการเรียงลำดับการกำจัดที่สมบูรณ์แบบโดยที่แต่ละจุดยอดมีเพื่อนบ้านก่อนหน้าไม่เกิน ดังนั้น ความเสื่อมจึงไม่เกิน treewidth และไม่เกิน pathwidth อย่างไรก็ตาม มีกราฟที่มีความเสื่อมที่จำกัดและ treewidth ที่ไม่จำกัด เช่นกราฟกริด^{[ 25 ]}${\displaystyle k}$${\displaystyle k}$

ข้อสันนิษฐาน ของBurr–Erdősเชื่อมโยงความเสื่อมของกราฟกับจำนวน Ramseyของ ซึ่ง เป็นค่าต่ำสุดที่การระบายสีขอบสองสีของกราฟสมบูรณ์ที่มีจุดยอดจะต้องมีสำเนาสีเดียวของโดยเฉพาะอย่างยิ่ง ข้อสันนิษฐานคือ สำหรับค่าคงที่ใดๆ ของจำนวน Ramsey ของกราฟที่เสื่อม จะเพิ่มขึ้นเป็นเส้นตรงตามจำนวนจุดยอดของกราฟ^{[ 26 ]}ข้อสันนิษฐานนี้ได้รับการพิสูจน์โดยLee (2017 ) ^{[ 27 ]}${\displaystyle G}$${\displaystyle G}$${\displaystyle n}$${\displaystyle n}$${\displaystyle G}$${\displaystyle k}$${\displaystyle k}$

กราฟจุดยอดใดๆ ที่มีความเสื่อมจะมี คลิกสูงสุดไม่เกิน เมื่อใดก็ตาม ที่และ^{[ 28 ]}ดังนั้นคลาสของกราฟที่มีความเสื่อมแบบจำกัดจึงกล่าวได้ว่ามีคลิกน้อย${\displaystyle n}$${\displaystyle d}$${\textstyle (nd)3^{d/3}}$${\displaystyle d\equiv 0{\bmod {3}}}$${\displaystyle n\geq d+3}$

แม้ว่าแนวคิดเรื่องความเสื่อมและจำนวนการระบายสีมักจะถูกพิจารณาในบริบทของกราฟจำกัด แต่แรงจูงใจดั้งเดิมของPaul ErdősและAndrás Hajnalคือทฤษฎีของกราฟอนันต์ สำหรับกราฟอนันต์เราอาจกำหนดจำนวนการระบายสีในลักษณะเดียวกับคำจำกัดความสำหรับกราฟจำกัด โดยเป็นจำนวนคาร์ดินัล ที่เล็กที่สุด ซึ่งมีการเรียงลำดับที่ดีของจุดยอดของ กราฟอนันต์ โดยที่แต่ละจุดยอดมีเพื่อนบ้านน้อยกว่าจำนวนเพื่อนบ้านที่อยู่ก่อนหน้าในการเรียงลำดับ ความไม่เท่าเทียมกันระหว่างจำนวนการระบายสีและจำนวนสียังคงใช้ได้ในบริบทอนันต์นี้เช่นกัน Erdős และ Hajnal ระบุว่า ณ วันที่ตีพิมพ์บทความของพวกเขาในปี 1966 เรื่องนี้เป็นที่รู้จักกันดีอยู่แล้ว^{[ 4 ]}${\displaystyle G}$${\displaystyle \alpha }$${\displaystyle G}$${\displaystyle \alpha }$

ความเสื่อมของเซตย่อยแบบสุ่มของโครงข่าย อนันต์ ได้รับการศึกษาภายใต้ชื่อ การแพร่ กระจายแบบบูตสแตรป (bootstrap percolation )

• ทฤษฎีกราฟ
• วิทยาศาสตร์เครือข่าย
• ทฤษฎีการซึมผ่าน
• โครงสร้างแกนกลาง-รอบนอก
• การคาดเดาของเซเรเซดา