กลับไปหน้าบทความ

อ่าน 7 นาที

กราฟโฮโมโลจี

ทฤษฎีกราฟ/ทฤษฎีความคล้ายคลึงกัน

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

กราฟโฮโมโลจี

ในโทโพโลยีเชิงพีชคณิตและทฤษฎีกราฟกราฟโฮโมโลยีอธิบายกลุ่มโฮโมโลยีของกราฟโดยที่กราฟถือเป็นปริภูมิโทโพโลยีมันทำให้แนวคิดเรื่องจำนวน "รู" ในกราฟเป็นทางการ มันเป็นกรณีพิเศษของซิมพลิเชียลโฮโมโลยีเนื่องจากกราฟเป็นกรณีพิเศษของซิมพลิเชียลคอมเพล็กซ์ เนื่องจากกราฟจำกัดเป็น 1-คอมเพล็กซ์ (กล่าวคือ 'หน้า' ของมันคือจุดยอด – ซึ่งมีมิติ 0 และขอบ – ซึ่งมีมิติ 1) กลุ่มโฮโมโลยีที่ไม่เป็นศูนย์มีเพียงกลุ่มที่ 0 และกลุ่มที่ 1 เท่านั้น[ 1 ]

กลุ่มโฮโมโลยีที่ 1

สูตรทั่วไปสำหรับกลุ่มโฮโมโลจีลำดับที่ 1 ของปริภูมิเชิงทอพอโลยีXคือ:ชม1(X):=เคอร์1/ฉัน2{\displaystyle H_{1}(X):=\ker \partial _{1}{\big /}\operatorname {im} \partial _{2}}ตัวอย่างด้านล่างนี้อธิบายสัญลักษณ์และแนวคิดเหล่านี้อย่างละเอียดโดยใช้กราฟ

ตัวอย่าง

ให้Xเป็นกราฟระบุทิศทางที่มี 3 จุดยอด{x, y, z}และ 4 เส้นเชื่อม{a: x → y, b: y → z, c: z → x, d: z → x}โดยมีวัฏจักรหลายวัฏจักร ดังนี้ :

  • หนึ่งวัฏจักรแสดงด้วยลูป a+b+c โดยเครื่องหมายบวกแสดงว่าขอบทุกด้านเดินทางไปในทิศทางเดียวกัน เนื่องจากการดำเนินการบวกเป็นการสลับที่ได้ เครื่องหมาย + จึงแสดงว่าลูป a + b + c, b + c + a และ c + a + b ล้วนเป็นวัฏจักรเดียวกัน
  • วัฏจักรที่สองแสดงด้วยลูป a + b + d
  • วงจรที่สามแสดงด้วยลูป c − d โดยที่เครื่องหมายลบแสดงว่าขอบ d ถูกเดินทางย้อนกลับ

ถ้าเราตัดระนาบตามเส้นโค้ง a + b + d แล้วตัดที่ c และ "เชื่อม" ที่ d เราจะได้การตัดตามเส้นโค้ง a + b + c ซึ่งสามารถแสดงได้ด้วยความสัมพันธ์ต่อไปนี้: (a + b + d) + (c − d) = (a + b + c) เพื่อกำหนดความสัมพันธ์นี้อย่างเป็นทางการ เราจึงกำหนดกลุ่มสลับที่ต่อไปนี้:

  • C คือกลุ่มอาเบเลียนอิสระที่สร้างขึ้นจากเซตของจุดยอด{x, y, z}แต่ละสมาชิกของC เรียกว่า โซ่ มิติศูนย์
  • C คือกลุ่มอาเบเลียนอิสระที่สร้างขึ้นจากเซตของขอบที่มีทิศทาง {a,b,c,d} แต่ละสมาชิกของC เรียกว่าโซ่หนึ่งมิติวงจรทั้งสามที่กล่าวถึงข้างต้นเป็นโซ่หนึ่งมิติ และความสัมพันธ์ (a + b + d) + (c − d) = (a + b + c) ก็เป็นจริงในกลุ่มC ด้วย

องค์ประกอบส่วนใหญ่ของC ไม่ใช่วัฏจักร ตัวอย่างเช่น a + b, 2a + 5b − c เป็นต้น ไม่ใช่วัฏจักร ในการกำหนดวัฏจักรอย่างเป็นทางการ เราต้องกำหนดขอบเขต ก่อน ขอบเขตของขอบจะถูกแทนด้วย1{\displaystyle \partial _{1}}ตัวดำเนินการและถูกกำหนดให้เป็นเป้าหมายลบด้วยแหล่งที่มา ดังนั้น1(เอ)=yx, 1()=zy, 1()=1()=xz.{\displaystyle \partial _{1}(a)=yx,~\partial _{1}(b)=zy,~\partial _{1}(c)=\partial _{1}(d)=xz.}ดังนั้น1{\displaystyle \partial _{1}}เป็นการแมปจากกลุ่มC ไปยังกลุ่มC เนื่องจาก a, b, c, d เป็นตัวสร้างของC ดังนั้น1{\displaystyle \partial _{1}}โดยธรรมชาติแล้วจะขยายไปสู่โฮโมมอร์ฟิซึมกลุ่มจากC ไปยังC ในโฮโมมอร์ฟิซึมนี้1(เอ++)=1(เอ)+1()+1()=(yx)+(zy)+(xz)=0{\displaystyle \partial _{1}(a+b+c)=\partial _{1}(a)+\partial _{1}(b)+\partial _{1}(c)=(yx)+(zy)+(xz)=0}ในทำนองเดียวกัน1{\displaystyle \partial _{1}}แมปวัฏจักรใดๆ ในC ไปยังองค์ประกอบศูนย์ของC กล่าวอีกนัยหนึ่ง เซตของวัฏจักรในC สร้างปริภูมิว่าง (เคอร์เนล)ของ1{\displaystyle \partial _{1}}ในกรณีนี้ แกนหลักของ1{\displaystyle \partial _{1}}มีตัวสร้างสองตัว ตัวหนึ่งสอดคล้องกับ a + b + c และอีกตัวหนึ่งสอดคล้องกับ a + b + d (วัฏจักรที่สาม c − d เป็นผลรวมเชิงเส้นของสองวัฏจักรแรก) ดังนั้นเคอร์1{\displaystyle \ker \partial _{1}}มีโครงสร้างเหมือนกับZ 2

ในปริภูมิโทโพโลยีทั่วไป เราจะกำหนดโซ่ที่มีมิติสูงกว่า โดยเฉพาะอย่างยิ่งC จะเป็นกลุ่มอาเบเลียนอิสระบนเซตของวัตถุ 2 มิติ อย่างไรก็ตาม ในกราฟไม่มีวัตถุดังกล่าว ดังนั้นC จึงเป็นกลุ่มที่ไม่มีนัยสำคัญ ดังนั้น ภาพของตัวดำเนินการขอบเขตที่สอง 2{\displaystyle \partial _{2}}เรื่องนี้ก็เป็นเรื่องเล็กน้อยเช่นกัน ดังนั้น:ชม1(X)=เคอร์1/ฉัน22/0=2{\displaystyle H_{1}(X)=\ker \partial _{1}{\big /}\operatorname {im} \partial _{2}\cong \mathbb {Z} ^{2}/\mathbb {Z} ^{0}=\mathbb {Z} ^{2}}สิ่งนี้สอดคล้องกับข้อเท็จจริงโดยสัญชาตญาณที่ว่ากราฟมี "รู" สองรู เลขชี้กำลังคือจำนวนรู

กรณีทั่วไป

ตัวอย่างข้างต้นสามารถขยายความทั่วไปไปยังกราฟเชื่อม ต่อใดๆ G = ( V , E ) ให้Tเป็นต้นไม้แผ่คลุมของGขอบทุกขอบในE \ Tสอดคล้องกับวัฏจักร ซึ่งก็คือวัฏจักรที่เป็นอิสระเชิงเส้น นั่นเอง ดังนั้น กลุ่มโฮโมโลยีแรกH ของกราฟ จึง เป็นกลุ่มอาเบเลียนอิสระที่มี ตัวสร้าง | E \ T |ตัว จำนวนนี้เท่ากับ| E || V | + 1 ดังนั้น: [ 1 ]ชม1(X)|อี||วี|+1.{\displaystyle H_{1}(X)\cong \mathbb {Z} ^{|E|-|V|+1}.}ในกราฟที่ไม่เชื่อมต่อกัน เมื่อCคือเซตของส่วนประกอบที่เชื่อมต่อกัน การคำนวณที่คล้ายกันจะแสดงให้เห็นว่า:ชม1(X)|อี||วี|+|ซี|.{\displaystyle H_{1}(X)\cong \mathbb {Z} ^{|E|-|V|+|C|}.}โดยเฉพาะอย่างยิ่ง กลุ่มแรกจะเป็นกลุ่มที่ไม่สำคัญก็ต่อเมื่อX เป็นป่าเท่านั้น

กลุ่มโฮโมโลยีที่ 0

สูตรทั่วไปสำหรับกลุ่มโฮโมโลยีลำดับที่ 0 ของปริภูมิเชิงทอพอโลยีXคือ:ชม0(X):=เคอร์0/ฉัน1{\displaystyle H_{0}(X):=\ker \partial _{0}{\big /}\operatorname {im} \partial _{1}}

ตัวอย่าง

กลับมาที่กราฟที่มี 3 จุดยอด{x, y, z}และ 4 ขอบ{a: x → y, b: y → z, c: z → x, d: z → x}จำได้ว่ากลุ่มC ถูกสร้างขึ้นจากเซตของจุดยอด เนื่องจากไม่มีองค์ประกอบมิติ (−1) ดังนั้นกลุ่มC จึงเป็นกลุ่มที่ไม่มีสมาชิกอื่น และด้วยเหตุนี้กลุ่มC ทั้งหมด จึงเป็นแกนหลักของตัวดำเนินการขอบเขตที่สอดคล้องกัน:เคอร์0=ซี0{\displaystyle \ker \partial _{0}=C_{0}}= กลุ่มอาเบเลียนอิสระที่สร้างขึ้นโดย{x, y, z}

ภาพของ1{\displaystyle \partial _{1}}ประกอบด้วยองค์ประกอบสำหรับแต่ละคู่ของจุดยอดที่เป็นขอบเขตของขอบ กล่าวคือ สร้างขึ้นจากผลต่าง{y − x, z − y, x − z}ในการคำนวณกลุ่มผลหารนั้น สะดวกที่จะนึกถึงองค์ประกอบทั้งหมดของ ฉัน1{\displaystyle \operatorname {im} \partial _{1}}ในฐานะ "เทียบเท่ากับศูนย์" ซึ่งหมายความว่า x, y และ z เทียบเท่ากัน – พวกมันอยู่ในชั้นความเทียบเท่า เดียวกัน ของผลหาร กล่าวอีกนัยหนึ่งคือชม0(X){\displaystyle H_{0}(X)}ถูกสร้างขึ้นโดยองค์ประกอบเดียว (จุดยอดใดก็ได้สามารถสร้างมันได้) ดังนั้นมันจึงสมมาตรกับZ

กรณีทั่วไป

ตัวอย่างข้างต้นสามารถนำไปใช้กับกราฟเชื่อมต่อ ใดๆ ก็ได้ โดยเริ่มจากจุดยอดใดๆ ก็สามารถไปยังจุดยอดอื่นๆ ได้โดยการเพิ่มนิพจน์ที่สอดคล้องกับขอบอย่างน้อยหนึ่งนิพจน์ (เช่น เริ่มจาก x สามารถไปยัง z ได้โดยการเพิ่ม y − x และ z − y) เนื่องจากองค์ประกอบของฉัน1{\displaystyle \operatorname {im} \partial _{1}}ถ้าค่าทั้งหมดเท่ากับศูนย์ นั่นหมายความว่าจุดยอดทั้งหมดของกราฟอยู่ในชั้นสมมูลเดียวกัน และดังนั้นชม0(X){\displaystyle H_{0}(X)}มีโครงสร้างเหมือนกับZ

โดยทั่วไป กราฟสามารถมีส่วนประกอบที่เชื่อมต่อกัน ได้หลายส่วน ให้Cเป็นเซตของส่วนประกอบเหล่านั้น ดังนั้น ส่วนประกอบที่เชื่อมต่อกันทุกส่วนจะเป็นชั้นสมมูลในกลุ่มผลหาร ดังนั้น:ชม0(X)|ซี|.{\displaystyle H_{0}(X)\cong \mathbb {Z} ^{|C|}.}สามารถสร้างได้จากทูเปิล| C |ใดๆ ของจุดยอด โดยแต่ละจุดยอดมาจากส่วนประกอบแต่ละส่วน

ความเหมือนกันที่ลดลง

บ่อยครั้งที่สะดวกที่จะสมมติว่าโฮโมโลยีลำดับที่ 0 ของกราฟเชื่อมต่อเป็นโฮโมโลยีที่ไม่สำคัญ (ดังนั้น ถ้ากราฟมีจุดเพียงจุดเดียว โฮโมโลยีทั้งหมดของกราฟนั้นก็จะเป็นโฮโมโลยีที่ไม่สำคัญ) ซึ่งนำไปสู่คำนิยามของโฮโมโลยีแบบลดรูป สำหรับกราฟหนึ่ง โฮโมโลยีลำดับที่ 0 แบบลดรูปคือ:ชม0~(X)|ซี|1.{\displaystyle {\tilde {H_{0}}}(X)\cong \mathbb {Z} ^{|C|-1}.}การ "ลดขนาด" นี้มีผลเฉพาะกับโฮโมโลจีลำดับที่ 0 เท่านั้น โฮโมโลจีที่ลดขนาดลงในมิติที่สูงกว่าจะเท่ากับโฮโมโลจีมาตรฐาน

ความเหมือนกันในมิติที่สูงกว่า

กราฟประกอบด้วยจุดยอด (องค์ประกอบ 0 มิติ) และขอบ (องค์ประกอบ 1 มิติ) เท่านั้น เราสามารถขยายกราฟไปสู่คอมเพล็กซ์เชิงซิมพลิเชียลแบบนามธรรมได้โดยการเพิ่มองค์ประกอบที่มีมิติสูงกว่า จากนั้น แนวคิดของโฮโมโลจีกราฟจะถูกขยายไปสู่แนวคิดของโฮโมโลจีเชิงซิมพลิเชีย

ตัวอย่าง

ในกราฟตัวอย่างข้างต้น เราสามารถเพิ่ม "เซลล์" สองมิติที่ล้อมรอบระหว่างขอบ c และ d ได้ สมมติให้เซลล์นี้เป็น A และกำหนดให้มีทิศทางตามเข็มนาฬิกา กำหนดให้เป็นกลุ่มอาเบเลียนอิสระที่สร้างขึ้นจากเซตของเซลล์สองมิติ ซึ่งในกรณีนี้คือเซตที่มีสมาชิกเพียงตัวเดียวA}แต่ละสมาชิกของC₂เรียกว่าโซ่สองมิติ

เช่นเดียวกับตัวดำเนินการขอบเขตจากC ไปยังC ซึ่งเราใช้สัญลักษณ์แทนด้วย1{\displaystyle \partial _{1}}มีตัวดำเนินการขอบเขตจากC ไปยังC ซึ่งเราใช้สัญลักษณ์แทนด้วย2{\displaystyle \partial _{2}}โดยเฉพาะอย่างยิ่ง ขอบเขตของเซลล์ 2 มิติ A คือขอบ 1 มิติ c และ d โดยที่ c อยู่ในทิศทางที่ "ถูกต้อง" และ d อยู่ในทิศทางที่ "กลับกัน" ดังนั้น:2(เอ)={\displaystyle \partial _{2}(A)=cd}ลำดับของโซ่และตัวดำเนินการขอบเขตสามารถนำเสนอได้ดังนี้:ซี22ซี11ซี0{\displaystyle C_{2}\xrightarrow {\partial _{2}} C_{1}\xrightarrow {\partial _{1}} C_{0}}การเพิ่มเซลล์ 2 มิติ A หมายความว่าขอบเขตของมัน c − d ไม่ได้แสดงถึงรูอีกต่อไป (มันเป็นโฮโมโทปิกกับจุดเดียว) ดังนั้น กลุ่มของ "รู" จึงมีตัวสร้างเพียงตัวเดียว นั่นคือ a + b + c (มันเป็นโฮโมโทปิกกับ a+b+d) กลุ่มโฮโมโลยีกลุ่มแรกจึงถูกกำหนดให้เป็นกลุ่มผลหาร :ชม1(X):=เคอร์1/ฉัน2{\displaystyle H_{1}(X):=\ker \partial _{1}{\big /}\operatorname {im} \partial _{2}}ที่นี่,เคอร์1{\displaystyle \ker \partial _{1}}เป็นกลุ่มของวัฏจักร 1 มิติ ซึ่งมีโครงสร้างเหมือนกับZ 2และฉัน2{\displaystyle \ชื่อผู้ดำเนินการ {im} \บางส่วน _{2}}คือกลุ่มของวัฏจักร 1 มิติที่เป็นขอบเขตของเซลล์ 2 มิติ ซึ่งมีโครงสร้างเหมือนกับZดังนั้น ผลหารH ของพวกมัน จึงมีโครงสร้างเหมือนกับZซึ่งสอดคล้องกับข้อเท็จจริงที่ว่าXตอนนี้มีรูเดียว ก่อนหน้านี้ ภาพของ2{\displaystyle \partial _{2}}เป็นกลุ่มที่ไม่สำคัญดังนั้นผลหารจึงเท่ากับเคอร์1{\displaystyle \ker \partial _{1}}สมมติว่าตอนนี้เราเพิ่มเซลล์ 2 มิติที่มีทิศทางอีกเซลล์หนึ่ง B ระหว่างขอบ c และ d โดยที่2(บี)=2(เอ)={\displaystyle \partial _{2}(\mathrm {B} )=\partial _{2}(\mathrm {A} )=cd}ตอนนี้C คือกลุ่มอาเบเลียนอิสระที่สร้างขึ้นโดย{A, B}สิ่งนี้ไม่เปลี่ยนแปลงH – มันยังคงสมมาตรกับZ ( Xยังคงมีรูมิติเดียว) แต่ตอนนี้C ประกอบด้วยวัฏจักรสองมิติ A − B ดังนั้น2{\displaystyle \partial _{2}}มีแกนกลางที่ไม่ธรรมดา วงจรนี้สร้างกลุ่มโฮโมโลยีที่สอง ซึ่งสอดคล้องกับข้อเท็จจริงที่ว่ามีรูสองมิติเพียงรูเดียว:ชม2(X):=เคอร์2{\displaystyle H_{2}(X):=\ker \partial _{2}\cong \mathbb {Z} }เราสามารถดำเนินการต่อและเพิ่มเซลล์ 3 เซลล์ ซึ่งเป็นวัตถุสามมิติที่เป็นของแข็ง (เรียกว่า C) ที่ถูกล้อมรอบด้วย A และ B กำหนดให้C เป็นกลุ่มอาเบเลียนอิสระที่สร้างขึ้นโดย{C}และตัวดำเนินการขอบเขต3:ซี3ซี2{\displaystyle \partial _{3}:C_{3}\to C_{2}}เราสามารถกำหนดทิศทางของ C ได้ดังนี้3(ซี)=เอบี{\displaystyle \partial _{3}(\mathrm {C} )=\mathrm {A} -\mathrm {B} }; โปรดสังเกตว่าขอบเขตของ C เป็นวัฏจักรในC ตอนนี้กลุ่มโฮโมโลยีที่สองคือ:ชม2(X):=เคอร์2/ฉัน30{\displaystyle H_{2}(X):=\ker \partial _{2}{\big /}\operatorname {im} \partial _{3}\cong {0}}ซึ่งสอดคล้องกับข้อเท็จจริงที่ว่าไม่มีช่องว่างสองมิติ (C "เติมเต็มช่องว่าง" ระหว่าง A และ B)

กรณีทั่วไป

โดยทั่วไป เราสามารถกำหนดสายโซ่ที่มีมิติใดก็ได้ หากมิติสูงสุดของสายโซ่คือkเราจะได้ลำดับของกลุ่มดังต่อไปนี้:ซีเคเคซีเค1ซี11ซี0{\displaystyle C_{k}\xrightarrow {\partial _{k}} C_{k-1}\cdots C_{1}\xrightarrow {\partial _{1}} C_{0}}สามารถพิสูจน์ได้ว่าขอบเขตใดๆ ของเซลล์มิติ ( k + 1) เป็น วัฏจักรมิติ kกล่าวอีกนัยหนึ่งคือ สำหรับk ใด ๆฉันเค+1{\displaystyle \ชื่อผู้ดำเนินการ {im} \บางส่วน _{k+1}}(กลุ่มของขอบเขตที่มีk + 1 องค์ประกอบ) บรรจุอยู่ในเคอร์เค{\displaystyle \ker \partial _{k}}(กลุ่มของ วัฏจักร kมิติ) ดังนั้น ผลหารเคอร์เค/ฉันเค+1{\displaystyle \ker \partial _{k}{\big /}\operatorname {im} \partial _{k+1}}มีนิยามที่ชัดเจน และนิยามว่าเป็น กลุ่มโฮโมโลจีลำดับที่ k :ชมเค(X):=เคอร์เค/ฉันเค+1{\displaystyle H_{k}(X):=\ker \partial _{k}{\big /}\operatorname {im} \partial _{k+1}}

ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Graph_homology&oldid=1360680439 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ กราฟโฮโมโลจี

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

กลุ่มโฮโมโลยีที่ 1

สูตรทั่วไปสำหรับกลุ่มโฮโมโลจีลำดับที่ 1 ของปริภูมิเชิงทอพอโลยี X คือ: ชม 1 ( X ) := เคอร์ ⁡ ∂ 1 / ฉัน ⁡ ∂ 2 {\displaystyle H_{1}(X):=\ker \partial _{1}{\big /}\operatorname {im} \partial _{2}}...

ตัวอย่าง

ให้ X เป็น กราฟระบุ ทิศทางที่มี 3 จุดยอด {x, y, z} และ 4 เส้นเชื่อม {a: x → y, b: y → z, c: z → x, d: z → x} โดยมีวัฏจักรหลาย วัฏจักร ดังนี้ :

กรณีทั่วไป

ตัวอย่างข้างต้นสามารถขยายความทั่วไปไปยัง กราฟเชื่อม ต่อใดๆ G = ( V , E ) ให้ T เป็น ต้นไม้แผ่คลุม ของ G ขอบทุกขอบใน E \ T สอดคล้องกับวัฏจักร ซึ่งก็คือวัฏจักร ที่เป็นอิสระเชิงเส้น นั่นเอง ดังนั้น กลุ่มโฮโมโลยีแรก H ของ กราฟ จึง เป็น กลุ่มอาเบเลียนอิสระ ที่มี...