Hierarchical Organization. We prove

Hierarchical Organization. We prove the following statement: At
any step of construction of the MST and graph G of genus g

k, if two elements are connected via at least one path in one of
the considered graphs, then they also are connected in the other
one. To this end, we must recall the concept of bridge: a link
between two elements is a bridge whenever the elements are
disconnected via any path in its absence. It follows from the
definition of MST that all links in the MST are bridges. Conversely,
for graphs with a fixed genus, we have the following
important property: If a bridge is inserted between two previously
unconnected regions of a graph G, characterized by the
genus g
k, then the genus of the graph obtained after the
insertion is still k. This property is straightforwardly proved as a
corollary of the Miller theorem (25, 26) by noting that the
addition of a bridge to a graph leaves unchanged the biconnected
components of the graph. The above property implies that if the
construction algorithm of G selects a link that is a bridge for the
graph at that step of construction, then the link is always added
to the graph. We now prove the above statement by induction.
In the following, we indicate as MSTm and Gm the graphs
constructed by using the similarity measure up to the mth row of
Sord. For the first two steps of construction, the statement is true:
MST2 and G2 graphs are always equal. Now suppose the
statement is true at the step m of construction, i.e., for Gm and
MSTm. For the step m 1, only four cases are possible:

ผลลัพธ์ (ไทย) 1:

องค์กรตามลำดับชั้น เราพิสูจน์คำสั่งต่อไปนี้: ที่ทุกขั้นตอนการก่อสร้างของ MST และกราฟ G g สกุลk ถ้าเชื่อมต่อผ่านเส้นทางหนึ่งน้อยหนึ่งในสององค์ประกอบพิจารณากราฟ แล้วพวกเขายังมีการเชื่อมต่อในอื่น ๆหนึ่ง ด้วยเหตุนี้ เราต้องจำแนวคิดของสะพาน: การเชื่อมโยงระหว่างองค์ประกอบที่สองเป็นสะพานตามองค์ประกอบเชื่อมต่อผ่านเส้นทางใด ๆ ในการขาดงาน มันตามจากการนิยามของ MST เชื่อมโยงทั้งหมดใน MST สะพาน ในทางกลับกันสำหรับกราฟที่มีสกุลถาวร เรามีดังนี้สำคัญ: ถ้าสะพานแทรกระหว่างสองก่อนหน้านี้กับภูมิภาคของกราฟ G ลักษณะการk g สกุล แล้วสกุลของกราฟที่ได้รับหลังจากการแทรกยังคงเป็น k พักนี้ดี ๆ พิสูจน์แล้วว่าเป็นการcorollary ของทฤษฎีบทของมิลเลอร์ (25, 26) โดยสังเกตว่า การนอกจากนี้ของสะพานจะเป็นกราฟใบไม่เปลี่ยนแปลง biconnectedส่วนประกอบของกราฟ พักข้างต้นหมายถึงว่าถ้าการเลือกก่อสร้างอัลกอริทึมของการเชื่อมโยงที่เป็นสะพานสำหรับการกราฟที่ขั้นตอนของงานก่อสร้าง การเชื่อมโยงถูกเพิ่มเสมอกราฟ เราตอนนี้พิสูจน์คำสั่งข้างต้น โดยการเหนี่ยวนำในต่อไปนี้ เราระบุเป็น MSTm และ Gm กราฟสร้างขึ้น โดยใช้การวัดความคล้ายคลึงกันขึ้นแถวเดือนSord สำหรับการสองขั้นตอนแรกของการก่อสร้าง ข้อเป็นจริง:กราฟ MST2 และ G2 เท่าเสมอกัน ตอนนี้ สมมติให้คำชี้แจงเป็นจริง m ขั้นตอนการก่อสร้าง เช่น สำหรับจีเอ็ม และMSTm สำหรับขั้นตอนม 1 เพียงสี่กรณีเป็นไปได้:

ผลลัพธ์ (ไทย) 2:

องค์การลำดับชั้น เราพิสูจน์ได้ว่าคำสั่งดังต่อไปนี้: ใน
ขั้นตอนของการก่อสร้างของ MST และกราฟ G ประเภทก. หรือไม่?
k ถ้าสององค์ประกอบที่มีการเชื่อมต่อผ่านเส้นทางอย่างน้อยหนึ่งในหนึ่งใน
กราฟพิจารณาแล้วพวกเขาก็ยังมีการเชื่อมต่อในอีก
หนึ่ง ด้วยเหตุนี้เราจะต้องจำแนวคิดของสะพาน: การเชื่อมโยง
ระหว่างสององค์ประกอบคือเมื่อใดก็ตามที่สะพานองค์ประกอบเป็นผู้
ตัดการเชื่อมต่อผ่านเส้นทางใด ๆ ในกรณีที่ไม่มีของ มันดังต่อไปจาก
ความหมายของ MST ว่าการเชื่อมโยงทั้งหมดใน MST สะพาน ตรงกันข้าม
สำหรับกราฟกับประเภทคงที่เราได้ดังต่อไปนี้
คุณสมบัติที่สำคัญ: หากสะพานจะถูกแทรกระหว่างสองก่อนหน้านี้
ภูมิภาคไม่เกี่ยวเนื่องกันของกราฟ G, โดดเด่นด้วย
สกุล G? K แล้วประเภทของกราฟได้รับหลังจากที่
แทรกยังคงเป็น K สถานที่แห่งนี้มีการพิสูจน์ตรงไปตรงมาเป็น
ข้อพิสูจน์ของมิลเลอร์ทฤษฎีบท (25 26) โดยสังเกตว่า
นอกเหนือจากสะพานกราฟใบไม่เปลี่ยนแปลง biconnected
ส่วนประกอบของกราฟ สถานที่ให้บริการดังกล่าวข้างต้นแสดงให้เห็นว่าถ้า
ขั้นตอนวิธีการก่อสร้างของ G เลือกการเชื่อมโยงที่เป็นสะพานสำหรับเป็น
กราฟในขั้นตอนของการก่อสร้างนั้นแล้วการเชื่อมโยงจะถูกเพิ่มเสมอ
ไปกราฟ ตอนนี้เราพิสูจน์ได้ว่าคำสั่งดังกล่าวโดยอุปนัย.
ในต่อไปนี้เราแสดงให้เห็นเป็น MSTm และ GM กราฟ
สร้างขึ้นโดยใช้ตัวชี้วัดความคล้ายคลึงกันถึงแถวของเดือน
SORD สำหรับสองขั้นตอนแรกของการก่อสร้างคำสั่งนี้เป็นจริง:
MST2 และกราฟ G2 อยู่เสมอเท่ากัน ตอนนี้สมมติว่า
คำสั่งที่เป็นความจริงในขั้นตอนเมตรของการก่อสร้างคือสำหรับจีเอ็มและ
MSTm สำหรับขั้นตอนม. 1 เพียงสี่กรณีเป็นไปได้:

ผลลัพธ์ (ไทย) 3:

องค์การแบบลำดับชั้น . เราพิสูจน์ได้ว่าข้อความต่อไปนี้ :ทุกขั้นตอนของการก่อสร้างของ MST และกราฟ G ประเภทก.เค ถ้าสององค์ประกอบจะเชื่อมต่อผ่านอย่างน้อยหนึ่งเส้นทางหนึ่งการพิจารณากราฟ แล้วพวกเขายังเกี่ยวข้องในอื่น ๆหนึ่ง สุดท้าย เราก็ต้องนึกถึงแนวคิดของสะพาน : การเชื่อมโยงระหว่างสององค์ประกอบเป็นสะพานที่มีองค์ประกอบการเชื่อมต่อผ่านทางใด ๆของเส้นทางในการขาดงาน มันคือ จากคำนิยามของ MST ที่การเชื่อมโยงทั้งหมดใน MST เป็นสะพาน ในทางกลับกันสำหรับกราฟที่มีสกุลถาวร เรามีดังต่อไปนี้คุณสมบัติที่สำคัญ : ถ้าสะพานจะถูกแทรกระหว่างสองก่อนหน้านี้วุ่นวายภูมิภาคของกราฟ G , ลักษณะโดยสกุล G K แล้วชนิดของกราฟที่ได้หลังจากแทรกยัง K . คุณสมบัตินี้เป็นตรงไปตรงมาพิสูจน์เป็นข้อพิสูจน์ของทฤษฎีบทมิลเลอร์ ( 25 , 26 ) โดยสังเกตว่าจากสะพานไปใบที่ biconnected กราฟไม่เปลี่ยนแปลงส่วนประกอบของกราฟ คุณสมบัติข้างต้น หมายถึงว่า ถ้าขั้นตอนวิธีการสร้าง G เลือกการเชื่อมโยงที่เป็นสะพานสำหรับกราฟ ในขั้นตอนของการก่อสร้าง แล้วเพิ่มลิงค์เสมอให้กราฟ ตอนนี้เราพิสูจน์ข้อความข้างต้นโดย inductionในต่อไปนี้เราแสดงเป็นกราฟ mstm และจีเอ็มสร้างโดยใช้ความคล้ายคลึงกันวัดได้ถึงเดือนแถวโสด . สำหรับสองขั้นตอนแรกของการก่อสร้าง คำสั่งที่เป็นจริง :mst2 G2 กราฟและเสมอเท่ากัน ตอนนี้คาดว่าคำสั่งเป็นจริงในขั้นตอนของการก่อสร้าง ได้แก่ เจนเนอรัล มอเตอร์ส ( และmstm . สำหรับขั้นตอนที่ 1 เพียง 4 รายที่เป็นไปได้ :