stanford-oval/wikipedia huggingface dataset:
ขุดคลองแลคูนาสยาม
รายได้

รายได้หลักของบริษัทมาจากการขายที่ดิน บริษัทจะออกหนังสือสำคัญของบริษัทให้เรียกว่า "ใบตรอก" ซึ่งถือเป็นความตกลงระหว่างบริษัทกับผู้ซื้อโดยรัฐบาลไม่ได้เกี่ยวข้อง บริษัทขายที่ได้ดีขึ้นปี พ.ศ. 2440 โดยขายที่ในเขตคลองรังสิตและคลอง 6 วาสายล่าง และขายที่ดินได้แพร่หลายขึ้นในปี พ.ศ. 2441–47 มีผู้มาซื้อที่ดินขนาดใหญ่เพื่อให้ชาวนาเช่า ลูกค้ากลุ่มนี้ได้แก่ เจ้านาย ข้าราชการ บาทหลวงในคริสต์ศาสนา และพ่อค้าชาวจีนในกรุงเทพ อย่างไรก็ตามในการขายที่ดิน รัฐบาลก็ได้พยายามเข้ามาควบคุมการตั้งราคาของบริษัทด้วย
บริษัทมีรายได้จาก ค่าธรรมเนียมประตูน้ำ สำหรับเรือที่ผ่านไปผ่านมา ประตูน้ำของบริษัทที่สำคัญมี 3 ประตูคือประตูน้ำจุฬาลงกรณ์, ประตูน้ำเสาวภาปิดกั้นคลองรังสิตทั้งสองด้าน และประตูบริษัทสมบูรณ์กั้นคลอง 6 วาสายล่าง
รายได้จากค่าเช่านา เป็นที่ดินที่ยังไม่ได้ขายหรือเป็นที่วิวาทยังไม่ได้ตัดสินตกลงเป็นของฝ่ายใด ซึ่งมีจำนวนไม่น้อย โดยในปี พ.ศ. 2433 พบว่ามีอยู่ประมาณ 20,000 ไร่ ตามรายงานของพระมหาโยธา ระบุว่า บริษัทมีรายได้จากการเก็บค่าเช่านาปีละ 40,000 บาท
บริษัทได้เงินค่าคลอง ที่บริษัทเรียกเก็บจากเจ้าของที่นาที่มีที่นาเป็นของตนเองอยู่แล้ว
ผลประโยชน์ที่ต้องตอบแทนรัฐบาล

จากสัญญาปี พ.ศ. 2431 ข้อ 8 ระบุว่าบริษัทจะต้องจ่ายค่าตอบแทนให้แก่รัฐบาลโดยคิดจากส่วนกำไรที่บริษัทได้รับร้อยละ 20  และไขข้อสัญญา พ.ศ. 2436 ข้อ 4 กำหนดว่าเงินซึ่งเรียกว่า "ค่าภาคหลวง" ให้บริษัทจ่ายให้รัฐบาลทุกปีจนกว่าคลองจะเสร็จ แต่เมื่อขายที่ดินได้เป็นจำนวนมาก บริษัทไม่ได้แบ่งส่วนกำไรให้รัฐบาลเลย ด้วยเหตุนี้รัฐบาลจึงยกเลิกสัญญา เปลี่ยนมาเป็นเรียกเก็บค่าธรรมเนียมตราจอง เมื่อมีการออกโฉนดตราจองที่ให้แก่บริษัทโดยเรียกเก็บไร่ละ 1 สลึง แต่พบหลักฐานว่าบริษัทค้างชำระค่าธรรมเนียมตราจอง
ข่าวลวงเรื่องไดไฮโดรเจนมอนอกไซด์

โครงสร้างโมเลกุลของน้ำ ไฮโดรเจนสองอะตอมและออกซิเจนหนึ่งอะตอม
สำหรับข้อมูลทางวิทยาศาสตร์ของน้ำ ดูที่ น้ำ (โมเลกุล)
ไดไฮโดรเจนมอนอกไซด์ (อังกฤษ: dihydrogen monoxide: DHMO) เป็นชื่อวิทยาศาสตร์หนึ่งของน้ำ ใช้ในการหลอกลวงหรือล้อเลียนทางวิทยาศาสตร์ เพื่อแสดงว่าข้อมูลที่ไม่สมบูรณ์หรือเพียงด้านเดียวสามารถสร้างความกลัวอย่างผิดๆได้อย่างไร การหลอกลวงนี้เริ่มต้นโดย Eric Lechner, Lars Norpchen และ Matthew Kaufman ในปี พ.ศ. 2532 ปรับปรุงโดย Craig Jackson ในปี พ.ศ. 2537 และเป็นที่กล่าวถึงในปี พ.ศ. 2540 จากการที่ Nathan Zohner วัย 14 ปีสามารถรวบรวมรายชื่อของนักเรียนมัธยมที่ต้องการแบนสารนี้ และสรุปลงในโครงงานที่ชื่อว่า "How Gullible Are We?" (เราโดนหลอกง่ายแค่ไหน?)
การหลอกลวงนี้กล่าวถึงผลกระทบด้านลบของน้ำ เช่นการจมน้ำ และ การกัดกร่อน ไดไฮโดรเจนมอนอกไซด์มีความหมายถึงสารที่มีไฮโดรเจนสองอะตอมและออกซิเจนหนึ่งอะตอม (H2O)
ชื่อทางเคมีอื่น ๆ ที่ถูกใช้เป็นข่าวลวงเช่น กรดไฮดรอกซิล (hydroxyl acid) และ ไฮโดรเจนออกไซด์ (hydrogen oxide) ก็หมายถึงน้ำเช่นกัน
แหล่งข้อมูลอื่น

DHMO.org – หน่วยงานวิจัย DHMO (อังกฤษ)
ข้อความที่ใช้ในการหลอกลวง เก็บถาวร 2008-05-09 ที่ เวย์แบ็กแมชชีน (อังกฤษ)
การตอบสนองจากนักศึกษาวิทยาลัย เก็บถาวร 1997-06-22 ที่ เวย์แบ็กแมชชีน (อังกฤษ)
Friends of Hydrogen Hydroxide – ข้อความส่งเสริมการใช้ DHMO (อังกฤษ)
บทความ About.com (อังกฤษ)
บทความ How Gullible Are We? (อังกฤษ)
ภาพยนตร์ Dihydrogen Monoxide ของ Kate Dalgleish และ Mikael Sydor เก็บถาวร 2009-06-06 ที่ เวย์แบ็กแมชชีน (อังกฤษ)
ข้อตกลงกระทำอัตวินิบาตกรรม

ข้อตกลงกระทำอัตวินิบาตกรรม (อังกฤษ: suicide pact) เป็นแผนที่ตกลงกันระหว่างปัจเจกบุคคลตั้งแต่สองคนขึ้นไปว่าจะกระทำอัตวินิบาตกรรม แผนนั้นอาจให้เสียชีวิตพร้อมกัน หรือแยกกันและเวลาใกล้เคียงกัน ข้อตกลงกระทำอัตวินิบาตกรรมเป็นมโนทัศน์ที่สำคัญในการศึกษาอัตวินิบาตกรรม และเกิดขึ้นตลอดประวัติศาสตร์ เช่นเดียวกับในบันเทิงคดี
โดยทั่วไปข้อตกลงกระทำอัตวินิบาตกรรมต่างจากการฆ่าตัวตายหมู่ เพราะการฆ่าตัวตายหมู่หมายถึงเหตุการณ์ซึ่งคนจำนวนมากกว่าฆ่าตัวตายด้วยกันด้วยเหตุผลทางอุดมการณ์เดียวกัน มักในบริบททางศาสนา การเมือง การทหารหรือกึ่งทหารเดียวกัน ในทางกลับกัน ข้อตกลงกระทำอัตวินิบาตกรรมปกติเกี่ยวข้องกับคนกลุ่มเล็ก (เช่น คู่สมรสหรือคู่รัก สมาชิกครอบครัวหรือเพื่อน) ซึ่งแรงจูงใจตรงแบบมักไม่เกี่ยวข้องกับอุดมการณ์
ส่วนข้อตกลงกระทำอัตวินิบาตกรรมที่มีการเจรจาบนอินเทอร์เน็ตระหว่างคนแปลกหน้าที่ไม่เคยรู้จักมาก่อน เรียก ข้อตกลงกระทำอัตวินิบาตกรรมอินเทอร์เน็ต
ขั้นตอนวิธีของเบลแมน-ฟอร์ด

| --- | --- |
ประเภท: ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียว
โครงสร้างข้อมูล: กราฟ
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด:  O(|V||E|)
ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด:  O(|V|)
ด ค ก
ขั้นตอนวิธีของเบลแมน-ฟอร์ด (อังกฤษ: Bellman-Ford Algorithm) เป็นขั้นตอนวิธีที่ใช้ในการแก้ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวสำหรับเส้นเชื่อมที่มีน้ำหนักใดๆ นอกจากนี้ขั้นตอนวิธียังสามารถตรวจพบวัฏจักรที่มีน้ำหนักรวมของเส้นเชื่อมเป็นลบ หรือที่เรียกว่าวัฏจักรเชิงลบ (อังกฤษ: Negative cycle) ซึ่งทำให้ปัญหาวิถีสั้นสุดไม่นิยาม ขั้นตอนวิธีนี้ถูกคิดค้นโดยนักพัฒนาชื่อริชาร์ด เบลแมน (Richard Bellman) และเลสเตอร์ ฟอร์ด จูเนียร์ (Lester Ford Jr)
แนวคิด

ขั้นตอนวิธีของเบลแมน-ฟอร์ดนั้นมีแนวคิดดังนี้
ใช้ได้กับกราฟที่มีน้ำหนักของเส้นเชื่อมทั้งบวกและลบ แต่ไม่สามารถใช้ได้กับกราฟที่มีวงจรเชิงลบ
กรณีที่ในกราฟนั้นมีวงจรเชิงลบจะแจ้งให้ผู้ใช้ทราบ
ใช้กำหนดการพลวัต
วิถีสั้นสุดจาก s ไป t ต้องไม่ผ่านปมซ้ำ และมีเส้นเชื่อมในวิถีอย่างมาก |v|-1 เส้น เมื่อ v แทนเส้นเชื่อมทั้งหมดในกราฟนั้น
ขั้นตอนวิธี

ขั้นตอนวิธีของเบลแมน-ฟอร์ดนั้นอยู่ในโครงสร้างพื้นฐานที่คล้ายกับขั้นตอนวิธีของไดค์สตรา โดยมีอัตราการเติบโตของการทำงานเป็น "O(|V||E|)" เมื่อ |V| และ |E| คือจำนวนปมและเส้นเชื่อมของกราฟนั้นๆ ตามลำดับ
เริ่มต้นพิจารณาจากแนวคิดพื้นฐานง่ายๆว่าเส้นทางที่สั้นที่สุดที่ไปยังปมทั้งหมดนั้นเป็นอนันต์ จากนั้นทำสัญลักษณ์ว่าได้ความยาวของเส้นทางเป็นศูนย์ ดังภาพ
จากนั้นพยายามเดินไปตามเส้นทางในทุกเส้นเชื่อมของกราฟระบุทิศทาง ถ้าพบว่าเมื่อไปตามเส้นเชื่อมนั้นแล้วตึงก็ให้พยายามที่จะผ่อนมัน
การผ่อนเส้นเชื่อมของกราฟ หมายถึง การตรวจสอบเพื่อดูว่าเส้นทางที่ไปยังปมนั้นไม่สามารถสั้นลงได้(เมื่อดูจากน้ำหนักของแต่ละเส้นเชื่อม) จากตัวอย่างกราฟข้างต้น เริ่มแรกเมื่อตรวจสอบที่เส้นทางจากปมที่ 1 ไปยังปมที่ 2 พบว่ามีน้ำหนักเส้นเชื่อมคือ 6 ซึ่งเป็นความยาวของเส้นทางที่สั้นที่สุดจากปมที่ 1 ไปยังปมที่ 2 ที่มีค่าน้อยกว่าอนันต์ ดังนั้นจึงแทนค่าอนันต์ในปมที่ 2 ด้วย 6 และเมื่อพิจารณาเส้นทางจากปมที่ 1 ไปยังปมที่ 4 พบว่ามีน้ำหนักเส้นเชื่อมคือ 7 ซึ่งเป็นความยาวของเส้นทางที่สั้นที่สุดจากปมที่ 1 ไปยังปมที่ 4 ที่มีค่าน้อยกว่าอนันต์ ดังนั้นจึงแทนค่าอนันต์ในปมที่ 4 ด้วย 7
ทำตามขั้นตอนนี้ไปเรื่อนๆเป็นจำนวน n - 1 ครั้ง เมื่อ n แทนจำนวนปมทั้งหมดในกราฟที่พิจารณา ดังนั้นในตัวอย่างนี้จะต้องใช้ขั้นตอนดังกล่างนี้ 4 ครั้ง ดังภาพ
รหัสเทียม

ข้อมูลนำเข้า คือ กราฟระบุทิศทางที่เส้นเชื่อมมีน้ำหนักที่มี v ปม
ข้อมูลส่งออก คือ ป้าย D[u] สำหรับปม u ใดๆบนกราฟ โดย D[u] คือระยะทางจากปม v ถึงปม u บนกราฟ ซึ่งกราฟนี้ต้องไม่มีวงจรเชิงลบ
1 กำหนดให้ D[v] มีค่าเท่ากับ 0
 2 ตั้งแต่ แต่ละปม u ไม่เท่ากับปม v ในกราฟ G
 3     กำหนดให้ D[u] มีค่าเป็นอนันต์
 4 ตั้งแต่ i := 1 ถึง n-1
 5     ตั้งแต่ ทุกเส้นเชื่อมที่ออกจากปม z
 6         ถ้า (D[u]+w(u,z))<D[z]
 7             จะให้ D[z]เก็บค่า D[u]+w(u,z) //w(u,z) คือการดำเนินการของการผ่อนเส้นเชื่อมกราฟ
 8         ถ้าไม่มีเส้นเชื่อมใดเลยที่ถูกผ่อน
 9             จะคืนค่าระยะทางจากปม v ถึงปม u ของแต่ละปม u
10        ไม่เช่นนั้น
11            จะคืนกลับมาว่า"กราฟนี้มีวงจรเชิงลบ"
การวิเคราะห์อัตราการเติบโต

จากรหัสเทียมข้างต้นจะพบว่าการดำเนินการของขั้นตอนวิธีของเบลแมน-ฟอร์ดนั้นจะมีการทำงานอยู่ 2 ส่วนหลัก คือ
วงวนที่มีการวนเพื่อตรวจสอบความตึงของน้ำหนักเส้นเชื่อมในกราฟ ซึ่งจะทำงานเป็นเวลานานเท่าจำนวนเส้นเชื่อมที่มี ดังนั้น จะใช้เวลาในการทำงานส่วนนี้เป็น O(|E|) เมื่อ E คือจำนวนเส้นเชื่อมของกราฟหนึ่งๆ
ส่วนการทำงานที่ต้องผ่านปมทุกปมในกราฟจะใช้เวลาทั้งหมดเป็น O(|V|) เมื่อ V คือจำนวนปมของกราฟหนึ่งๆ
เพราะฉะนั้นจึงสรุปได้ว่าชั้นตอนวิธีของเบลแมน-ฟอร์ดมีอัตราการเติบโตเท่ากับ O(|V||E|)
การนำไปใช้งาน

วิถีสั้นสุดในกราฟมีทิศทาง
โพรโตคอลเลือกเส้นทางแบบตารางระยะทาง (RIP)
ตัวอย่างรหัสในภาษาต่างๆ

C
C++ เก็บถาวร 2011-10-06 ที่ เวย์แบ็กแมชชีน
Java เก็บถาวร 2013-02-17 ที่ เวย์แบ็กแมชชีน
PHP เก็บถาวร 2011-09-12 ที่ เวย์แบ็กแมชชีน
Python
ดูเพิ่ม

ULearn การออกแบบอัลกอริทึม (สมชาย ประสิทธิ์จูตระกูล)
ภาพเคลื่อนไหว ขั้นตอนวิธีของเบลแมน-ฟอร์ด
Bellman-ford Algorithm E-leaning(Introduction to Algorithms)
ขั้นตอนวิธีของไดค์สตรา เป็นขั้นตอนวิธีที่ใช้ในการหาระยะทางเส้นทางสั้นสุดของคู่ปมใดๆ สำหรับกราฟที่มีความยาวของเส้นเชื่อมไม่เป็นลบ
ขั้นตอนวิธีของจอห์นสัน เป็นขั้นตอนวิธีที่ใช้หาเส้นทางสั้นที่สุดระหว่างทุกคู่จุด ในกราฟระบุทิศทางที่มีเส้นเชื่อมน้อย ขั้นตอนวิธีนี้สามารถใช้น้ำหนักของเส้นเชื่อมเป็นจำนวนลบได้ แต่ต้องไม่มีวงรอบที่น้ำหนักติดลบอยู่ด้วย
ขั้นตอนวิธีของฟลอยด์-วอร์แชล เป็นขั้นตอนวิธีการวิเคราะห์กราฟเพื่อที่จะหาระยะทางของเส้นทางสั้นสุดในกราฟที่มีน้ำหนักของเส้นเชื่อมเป็นบวก หรือ น้ำหนักของเส้นเชื่อมเป็นลบ แต่ไม่สามารถหาได้ถ้ามีวงจรลบ
แหล่งข้อมูลอื่น

การออกแบบอัลกอริทึม (สมชาย ประสิทธิ์จูตระกูล)
ULearn การออกแบบอัลกอริทึม (สมชาย ประสิทธิ์จูตระกูล)
Algo Wiki[ลิงก์เสีย]
ขั้นตอนวิธีฮอปครอฟท์-คาร์พ

ขั้นตอนวิธีฮอปครอฟท์-คาร์พ (อังกฤษ: Hopcroft–Karp algorithm) เป็นขั้นตอนวิธี ที่มีข้อมูลนำเข้าเป็นกราฟสองส่วน และมีผลลัพธ์เป็นจำนวนการจับคู่ที่มากที่สุด นั่นคือเซ็ตของเส้นเชื่อมที่มากที่สุดที่เป็นไปได้โดยที่ไม่มีเส้นเชื่อมสองเส้นที่ต่างกันใด ๆ เชื่อมไปยังจุดเดียวกัน ใช้เวลาในการทำงานเป็น  O(m{\sqrt {n}}) ในกรณีแย่สุด, โดย  O คือ สัญกรณ์โอใหญ่,  m คือ จำนวนของเส้นเชื่อมในกราฟ, และ  n คือจำนวนจุดในกราฟ สำหรับกราฟซับซ้อน ใช้เวลาในการทำงานเป็น  O(n^{\frac {5}{2}}) และสำหรับกราฟแบบสุ่ม ใช้เวลาในการทำงานเป็นเชิงเส้น
ขั้นตอนวิธีฮอปครอฟท์-คาร์พคิดค้นโดยจอห์น ฮอปครอฟท์และริชาร์ด คาร์พ เป็นขั้นตอนวิธีสำหรับการจับคู่เช่นเดียวกับขั้นตอนวิธีฮังกาเรียนและเอ็ดมอนส์ (1993) harvtxt error: no target: CITEREFเอ็ดมอนส์1993 (help) ขั้นตอนวิธีฮอปครอฟท์-คาร์พทำโดยการเพิ่มขนาดของการจับคู่ซ้ำ ๆ โดยการหาวิถีแต่งเติม ใช้การวนซ้ำ  O({\sqrt {n}}) รอบ โดนหลักการเดียวกันนี้ยังใช้พัฒนาขั้นตอนวิธีที่ซับซ้อนขึ้นสำหรับการจับคู่ในกราฟที่ไม่ใช่กราฟสองส่วน โดยใช้เวลาในการทำงานเหมือนกับขั้นตอนวิธีฮอปครอฟท์-คาร์พ
วิถีแต่งเติม

แนวคิดพื้นฐานของขั้นตอนวิธีนี้ขึ้นอยู่กับวิถีแต่งเติม
จุดอิสระ คือ จุดที่ไม่เชื่อมต่อกับเส้นเชื่อมใด ๆ ในการจับคู่  M
วิถีแต่งเติม คือ วิถีที่เริ่มต้นจากจุดอิสระไปยังจุดอิสระ โดยวิถีนี้ จะผ่านเส้นเชื่อมทั้งที่มีการจับคู่อยู่แล้วและยังไม่มีการจับคู่สลับกันไป
n คือ ขนาดของการจับคู่  M
P คือ วิถีแต่งเติมที่สัมพันธ์กับ  M
จะได้ว่า ผลต่างสมมาตรของเซ็ตของเส้นเชื่อม  M\oplus P ทำให้เกิดการจับคู่ที่มีขนาด  n+1 ดังนั้น จะใช้วิถีแต่งเติมเพื่อขยายขนาดของการจับคู่ได้
ในทางกลับกัน สมมติว่าการจับคู่  M ไม่ใช่วิธีที่ดีที่สุด ให้ผลต่างสมมาตร  P=M\oplus M^{*} โดย  M^{*} คือการจับคู่ที่ดีที่สุด จะได้  P คือวิถีแต่งเติมหลายๆวิถีที่ไม่ต่อเนื่องกัน และจำนวนวิถีใน  P เท่ากับความแตกต่างของขนาดของ  M และ  M* ดังนั้น จะหยุดขั้นตอนวิธีนี้และจะได้การจับคู่  M ที่ดีที่สุดเมื่อไม่สามารถหาวิถีแต่งเติมได้
วิถีแต่งเติมในปัญหาการจับคู่ มีลักษณะคล้ายกับวิถีแต่งเติมในปัญหาการไหลมากสุด นั่นคือวิถีแต่งเติมจะเพิ่มขนาดของการไหล โดยสามารถเปลี่ยนแปลงปัญหาการจับคู่กราฟสองส่วนเป็นปัญหาการไหลมากสุดได้ เช่น การเปลี่ยนวิถีทดแทนในปัญหาการจับคู่เป็นวิถีแต่งเติมในปัญหาการไหล การนำเทคนิคที่ใช้ในขั้นตอนวิธีฮอปครอฟท์-คาร์พ ไปใช้ในข่ายงานการไหล รู้จักกันในชื่อขั้นตอนวิธีของดีนิซ
ขั้นตอนวิธี

ให้  U และ  Vเป็นเซ็ตที่แบ่งกราฟสองส่วน  G ออกเป็นสองส่วน และให้เซ็ต  M แสดงการจับคู่ใด ๆ จาก  U ไปยัง  V
ขั้นตอนวิธีนี้แบ่งการทำงานเป็นวัฏภาค โดยทุกๆวัฏภาคมีขั้นตอนดังนี้
ใช้การค้นหาตามแนวกว้างแบ่งจุดในกราฟเป็นชั้น โดยเริ่มต้นค้นหาจากจุดอิสระใน  U และถือว่าจุดที่เริ่มค้นหาเป็นชั้นแรก ในระดับแรกของการค้นหาตามแนวกว้างจะมีการท่องไปยังเส้นเชื่อมที่ไม่มีการจับคู่เท่านั้น (นั่นคือ  U ไม่มีการเชื่อมต่อกับเส้นเชื่อมที่มีการจับคู่ใดๆ) และในระดับต่อๆไปของการค้นหาตามแนวกว้าง การท่องไปในเส้นเชื่อมจะต้องทำระหว่างเส้นเชื่อมที่มีการจับคู่และเส้นเชื่อมที่ไม่มีการจับคู่ นั่นคือ เมื่อการค้นหาสิ้นสุดลง จากจุดใน  U จะท่องไปในเส้นเชื่อมที่ไม่มีการจับคู่เท่านั้น แต่จากจุดใน  V จะท่องไปในเส้นเชื่อมที่มีการจับคู่แล้วเท่านั้น การค้นหาจะสิ้นสุดเมื่อพบชั้นแรกที่มีจุดอิสระใน  V ที่ถูกเข้าถึงแล้วอย่างน้อยหนึ่งจุด กำหนดให้เป็นชั้น  k
นำทุกๆจุดอิสระใน  V ที่ระดับชั้น  k ใส่ไปในเซ็ต  F นั่นคือ จุด  v จะถูกใส่ใน  F ก็ต่อเมื่อจุดนั้นถูกพบในวิถีแต่งเติมที่สั้นที่สุดซึ่งได้มาจากการค้นหาตามแนวกว้าง
ทำการหาจำนวนวิถีแต่งเติมความยาว  k ที่มากที่สุดที่ไม่ติดกัน โดยการค้นหาตามแนวลึกจาก  F ไปยังจุดอิสระใน  U โดยการใช้ชั้นจากการค้นหาตามแนวกว้างเพื่อเป็นแนวทางการค้นหา การค้นหาตามแนวลึกจะค้นไปยังจุดที่ยังไม่เคยพบในชั้นก่อนหน้า และในต้นไม้ของค้นหาตามแนวลึก จุดเชื่อมต่อใดๆในวิถีที่ได้จะเชื่อมต่อระหว่างเส้นเชื่อมที่ถูกจับคู่แล้วและเส้นเชื่อมที่ยังไม่ได้จับคู่เท่านั้น เมื่อพบวิถีแต่งเติมที่เริ่มจากจุดใน  F แล้ว จะทำการค้นหาตามแนวลึกใหม่ โดยทำจากจุดเริ่มต้นถัดไปใน  F
ทุกๆวิถีที่ได้มาจะถูกนำไปเพิ่มขนาดของ  M
ขั้นตอนวิธีนี้จะสิ้นสุดเมื่อไม่พบวิถีแต่งเติมจากการค้นหาตามแนวกว้างในวัฏภาคใดๆ
วิเคราะห์การทำงาน

แต่ละวัฏภาคประกอบด้วยการค้นหาตามแนวกว้างหนึ่งครั้งและการค้นหาตามแนวลึกหนึ่งครั้ง ดังนั้นในวัฏภาคหนึ่งๆจะใช้เวลาเชิงเส้น เพราะฉะนั้น สำหรับ  {\sqrt {n}} วัฏภาคแรก ในกราฟที่มี  n จุด และ m เส้นเชื่อม จะใช้เวลาทั้งหมด  O(m{\sqrt {n}})
โดยแสดงได้ว่า ในทุกๆวัฏภาค ความยาวของวิถีแต่งเติมที่สั้นที่สุดจะมีการเพิ่มความยาวขึ้นเสมอ นั่นคือ ในแต่ละวัฏภาค วิถีแต่งเติมอื่นๆที่เหลืออยู่ต้องมีความยาวมากกว่าความยาวปัจจุบันเสมอ เพราะฉะนั้นเมื่อ  {\sqrt {n}} วัฏภาคแรกในขั้นตอนวิธีสิ้นสุดลง วิถีแต่งเติมที่สั้นที่สุดจะมีเส้นเชื่อมอย่างน้อย  {\sqrt {n}} เส้นเชื่อม อย่างไรก็ตามผลต่างสมมาตรระหว่างการจับคู่ที่ดีที่สุดและการจับคู่  M ที่ได้มาจากแต่ละวัฏภาค จะก่อให้เกิดวิถีแต่งเติมหลายๆวิถีที่ไม่ต่อเนื่องกัน นั่นคือ ถ้าแต่ละวิถีในเซ็ตมีความยาวอย่างน้อยเท่ากับ  {\sqrt {n}} แล้ว จะมีวิถีได้อย่างมากที่สุดจำนวน  {\sqrt {n}} วิถี และขนาดของการจับคู่ที่ดีที่สุดจะมีความแตกต่างจากขนาดของ  M ได้อย่างมากเท่ากับ  {\sqrt {n}} เส้นเชื่อม และเนื่องจากว่าทุกวัฏภาคของขั้นตอนวิธีนี้จะมีการเพิ่มขนาดของการจับคู่เสมอ ดังนั้นก่อนที่ขั้นตอนวิธีจะสิ้นสุด จะมีวัฏภาคเพิ่มได้อย่างมากที่สุดอีกจำนวน  {\sqrt {n}} วัฏภาค
จะได้ว่า ขั้นตอนวิธีนี้มีการทำงานอย่างมากที่สุด  2{\sqrt {n}} วัฏภาค ดังนั้น จะได้เวลาทั้งหมดในการทำงานคือ  O(m{\sqrt {n}}) สำหรับกรณีแย่สุด
อย่างไรก็ตาม ในหลายๆกรณี เวลาที่ใช้โดยขั้นตอนวิธีนี้อาจจะเร็วกว่าในการวิเคราะห์กรณีแย่สุด เช่น ในกรณีเฉลี่ยสำหรับกราฟกระจายสองส่วนแบบกราฟสุ่ม Bast et al. (2006) harvtxt error: no target: CITEREFBastMehlhornSchaferTamaki2006 (help) ได้แสดงว่า ในการจับคู่ที่ไม่ใช่การจับคู่ที่ดีที่สุด วิถีแต่งเติมที่ได้มีโอกาสสูงที่จะมีความยาวเป็นลอการิทึม (พัตนาจากผลของ Motwani (1994) harvtxt error: no target: CITEREFMotwani1994 (help)) ดังนั้น สำหรับกราฟเหล่านี้ ขั้นตอนวิธีฮอปครอฟท์-คาร์พ จะมี  O(\log(n)) วัฏภาคและจะมีเวลาในการทำงานเท่ากับ  O(m\log(n))
เปรียบเทียบกับขั้นตอนวิธีจับคู่กราฟสองส่วนอื่นๆ

สำหรับกราฟกระจายขั้นตอนวิธีฮอปครอฟท์-คาร์พ เป็นขั้นตอนวิธีที่มีประสิทธิภาพดีที่สุดในกรณีแย่สุด แต่สำหรับกราฟซับซ้อนขั้นตอนวิธีโดย Alt et al. (1991) harvtxt error: no target: CITEREFAltBlumMehlhornPaul1991 (help) สามารถทำงานได้ดีกว่าเล็กน้อย คือ  O(n^{1.5}({\frac {m}{\log(n)}})^{0.5}) โดยเป็นขั้นตอนวิธีที่มีพื้นฐานจากขั้นตอนวิธีการไหลมากสุดดัน-ติดป้ายซ้ำซึ่งหลังจากการจับคู่โดยขั้นตอนวิธีนี้แล้วจะสลับมาใช้วิธีฮอปครอฟท์-คาร์พ
มีผู้ทดลองเปรียบเทียบขั้นตอนวิธีจับคู่กราฟสองส่วน ผลลัพธ์ที่ได้ปรากฏว่าขั้นตอนวิธีฮอปครอฟท์-คาร์พไม่ดีเหมือนกับในทฤษฎี เมื่อเทียบกับแผนการทางกว้างและแผนการทางลึกเพื่อหาวิถีแต่งเติม และเทคนิกดัน-ติดป้ายซ้ำ
กราฟที่ไม่ใช่กราฟสองส่วน

การหาจำนวนสมาชิกจับคู่มากสุดในกราฟที่ไม่ใช่กราฟสองส่วน สามารถใช้แนวคิดเดียวกับการหาจำนวนมากสุดของวิถีแต่งเติมที่สั้นที่สุดได้ ดังนั้นจะได้ขั้นตอนวิธีที่มี  O({\sqrt {n}}) วัฏภาค อย่างไรก็ตาม สำหรับกราฟที่ไม่ใช่กราฟสองส่วน การหาวิถีแต่งเติมในแต่ละวัฏภาคทำได้ยากและช้ากว่า Micali & Vazirani (1980) harvtxt error: no target: CITEREFMicaliVazirani1980 (help) ได้แสดงถึงขั้นตอนวิธีในแต่ละวัฏภาคโดยใช้เวลาเชิงเส้นในกราฟที่ไม่ใช่กราฟสองส่วน ซึ่งใช้เวลาเท่ากับขั้นตอนวิธีฮอปครอฟท์-คาร์พ แต่เทคนิกที่ไมคาไล-วาซิรานีใช้นั้นมีความซับซ้อนและยังไม่ได้รับการพิสูจน์อย่างสมบูรณ์ นอกจากนี้ยังมีขั้นตอนวิธีที่อื่น ๆ อีก
รหัสเทียม

1 /*
 2   G = G1 ∪ G2 ∪ {จุดว่าง}
 3   G1 และ G2 คือส่วนย่อยในกราฟสองส่วน และ จุดว่าง เป็นจุดพิเศษ
 4 */
 5
 6 ฟังก์ชัน ค้นหาตามแนวกว้าง()
 7     สำหรับทุกๆจุด v ใน G1
 8         ถ้า คู่ของ v เท่ากับ จุดว่าง
 9             กำหนด ระยะทางของ v เป็น 0
10             เพิ่ม v ลงในแถวคอย
11         ไม่เช่นนั้น
12             กำหนด ระยะทางของ v เป็น ∞
13     กำหนด ระยะทางของ จุดว่าง เป็น ∞
14     ในขณะที่ แถวคอยไม่ว่าง
15         กำหนด v เป็น จุดหน้าสุดของแถวคอย และนำจุดหน้าสุดของแถวคอยออกไป
16         สำหรับทุกๆจุด u ที่มีเส้นเชื่อมกับ v
17             ถ้า ระยะทางของคู่ของ u เท่ากับ ∞
18                 กำหนด ระยะทางของคู่ของ u เป็น ระยะทางของ v + 1
29                 เพิ่ม คู่ของ u ลงในแถวคอย
20     คืนค่า ระยะทางของจุดว่างเท่ากับ ∞ ใช่หรือไม่
21
22 ฟังก์ชัน ค้นหาตามแนวลึก (v)
23     ถ้า v ไม่เท่ากับ จุดว่าง
24         สำหรับทุกๆจุด u ที่มีเส้นเชื่อมกับ v
25             ถ้า ระยะทางของคู่ของ u เท่ากับ ระยะทางของ v + 1
26                 ถ้า ค้นหาตามแนวลึก(คู่ของ u) เป็นจริง
27                     กำหนด คู่ของ u เป็น v
28                     กำหนด คู่ของ v เป็น u
39                     คืนค่า จริง
30         กำหนด ระยะทางของ v เป็น ∞
31         คืนค่า เท็จ
32     คืนค่า จริง
33
34 ฟังก์ชัน ฮอปครอฟท์-คาร์พ
35     สำหรับทุกๆจุด v ใน G
36         กำหนด คู่ของ v เป็น จุดว่าง
37     กำหนด จำนวนการจับคู่ เป็น 0
38     ในขณะที่ ค้นหาตามแนวกว้าง() เป็นจริง
49         สำหรับทุกๆจุด v ใน G1
40             ถ้า คู่ของ v เท่ากับ จุดว่าง
41                 ถ้า ค้นหาตามแนวลึก(v) เป็นจริง
42                     กำหนด จำนวนการจับคู่ เป็น จำนวนการจับคู่ + 1
44     คืนค่า จำนวนการจับคู่
ดูเพิ่ม

ทฤษฎีกราฟ
อภิธานศัพท์ทฤษฎีกราฟ
กราฟสองส่วน
ปัญหาการไหลมากสุด
การค้นหาตามแนวกว้าง
ขั้นตอนวิธีฮังกาเรียน
ขั้นตอนวิธีของดีนิซ
ขั้วโลกใต้

ขั้วโลกใต้ทางภูมิศาสตร์
ขั้วโลกใต้แม่เหล็ก (2007)
ขั้วโลกใต้สนามแม่เหล็ก (2005)
ขั้วโลกใต้ที่ไกลที่สุด
ภาพขั้วโลกใต้ของนาซาในปีค.ศ.2005.
ขั้วโลกใต้ (อังกฤษ: South Pole) เป็นจุดที่อยู่ทางทิศใต้สุดของโลก
ทางภูมิศาสตร์

ขั้วโลกใต้ทางภูมิศาสตร์ (Geographic South Pole) เป็นหนึ่งในสองจุดที่แกนหมุนของโลกตั้งฉากกับพื้นผิวโลก (อีกจุดหนึ่งคือ ขั้วโลกเหนือทางภูมิศาสตร์) อยู่ที่ละติจูด 90 องศาใต้ บนแผ่นดินของทวีปแอนตาร์กติกา
มนุษย์คนแรกที่สามารถไปถึงขั้วโลกใต้ทางภูมิศาตร์ได้ คือ นักสำรวจชาวนอร์เวย์ ชื่อ โรอัลด์ อะมุนด์เซน (Roald Amundsen) เมื่อวันที่ 14 ธันวาคม ค.ศ. 1911
ข้อมูลภูมิอากาศของขั้วโลกใต้

| ข้อมูลภูมิอากาศของขั้วโลกใต้> เดือน | ข้อมูลภูมิอากาศของขั้วโลกใต้> ม.ค. | ข้อมูลภูมิอากาศของขั้วโลกใต้> ก.พ. | ข้อมูลภูมิอากาศของขั้วโลกใต้> มี.ค. | ข้อมูลภูมิอากาศของขั้วโลกใต้> เม.ย. | ข้อมูลภูมิอากาศของขั้วโลกใต้> พ.ค. | ข้อมูลภูมิอากาศของขั้วโลกใต้> มิ.ย. | ข้อมูลภูมิอากาศของขั้วโลกใต้> ก.ค. | ข้อมูลภูมิอากาศของขั้วโลกใต้> ส.ค. | ข้อมูลภูมิอากาศของขั้วโลกใต้> ก.ย. | ข้อมูลภูมิอากาศของขั้วโลกใต้> ต.ค. | ข้อมูลภูมิอากาศของขั้วโลกใต้> พ.ย. | ข้อมูลภูมิอากาศของขั้วโลกใต้> ธ.ค. | ข้อมูลภูมิอากาศของขั้วโลกใต้> ทั้งปี |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| อุณหภูมิสูงสุดที่เคยบันทึก °C (°F) | -14 (7) | -20 (-4) | -26 (-15) | -27 (-17) | -30 (-22) | -31 (-24) | -33 (-27) | -32 (-26) | -29 (-20) | -29 (-20) | -18 (-0) | -13 (9) | −13.6 (7.5) |
| อุณหภูมิสูงสุดเฉลี่ย °C (°F) | -25.9 (-14.6) | -38.1 (-36.6) | -50.3 (-58.5) | -54.2 (-65.6) | -53.9 (-65) | -54.4 (-65.9) | -55.9 (-68.6) | -55.6 (-68.1) | -55.1 (-67.2) | -48.4 (-55.1) | -36.9 (-34.4) | -26.5 (-15.7) | −46.3 (−51.3) |
| อุณหภูมิต่ำสุดเฉลี่ย  °C (°F) | -29.4 (-20.9) | -42.7 (-44.9) | -57.0 (-70.6) | -61.2 (-78.2) | -61.7 (-79.1) | -61.2 (-78.2) | -62.8 (-81) | -62.5 (-80.5) | -62.4 (-80.3) | -53.8 (-64.8) | -40.4 (-40.7) | -29.3 (-20.7) | −52.0 (−61.6) |
| อุณหภูมิต่ำสุดที่เคยบันทึก °C (°F) | -41 (-42) | -57 (-71) | -71 (-96) | -75 (-103) | -78 (-108) | -82 (-116) | -80 (-112) | -77 (-107) | -79 (-110) | -71 (-96) | -55 (-67) | -38 (-36) | −82.8 (−117) |
| จำนวนชั่วโมงที่มีแดด | 558 | 480 | 217 | 0 | 0 | 0 | 0 | 0 | 60 | 434 | 600 | 589 | 2,938 |
แหล่งที่มา 1: 
แหล่งที่มา 2: Cool Antarctica
ดูเพิ่ม

ขั้วโลกเหนือ
ทวีปแอนตาร์กติกา
แหล่งข้อมูลอื่น

NOAA South Pole Webcam
360° Panoramas of the South Pole เก็บถาวร 2015-04-28 ที่ เวย์แบ็กแมชชีน
Images of this location are available at the Degree Confluence Project
South Pole Photo Gallery เก็บถาวร 2005-09-05 ที่ เวย์แบ็กแมชชีน
Poles เก็บถาวร 2010-04-26 ที่ เวย์แบ็กแมชชีน by the Australian Antarctic Division
The Antarctic Sun - Online news source for the U.S. Antarctic Program
Big Dead Place เก็บถาวร 2016-06-25 ที่ เวย์แบ็กแมชชีน
UK team makes polar trek history - BBC News article on first expedition to Pole of Inaccessibility without mechanical assistance
Listen to Ernest Shackleton describing his 1908 South Pole Expedition, and read more about the recording on [australianscreen online].
The recording describing Shackleton's 1908 South Pole Expedition was added to the National Film and Sound Archive's Sounds of Australia Registry in 2007
90°S 0°W﻿ / ﻿90°S -0°E﻿ / -90; -0
ขั้วโลก

ขั้วโลก (อังกฤษ: geographical pole หรือ geographic pole) หมายถึงจุดสองจุด—ขั้วโลกเหนือและขั้วโลกใต้—บนพื้นผิวของดาวเคราะห์หรือวัตถุหมุนอื่น อันเป็นที่ซึ่งแกนหมุนบรรจบกับพื้นผิวของวัตถุนั้น ขั้วโลกเหนือจะทำมุม 90° และอยู่เหนือเส้นศูนย์สูตร ในขณะที่ขั้วโลกใต้จะทำมุม 90° และอยู่ใต้เส้นศูนย์สูตร
ขั้วโลกอาจมีความเป็นไปได้ที่จะคาดเคลื่อนเล็กน้อยเนื่องจากการหมุนของวัตถุนั้นเอง ขั้วโลกเหนือและใต้ทางกายภาพที่แท้จริงของโลกนั้นจะอาจเปลี่ยนตำแหน่งไปได้ในระยะทางไม่กี่เมตรเมื่อเวลาผ่านไป ปรากฏการณ์ดังกล่าวมีความชัดเจนจากการหมุนควงของวิษุวัติของโลก ซึ่งองศาของดาวเคราะห์ (ทั้งแกนหมุนและพื้นผิวต่างก็เคลื่อนที่ไปพร้อมกัน) อาจเปลี่ยนแปลงตำแหน่งได้อย่างช้า ๆ เมื่อเวลาผ่านไปนับหมื่นปี
อย่างไรก็ตาม วิชาการเขียนแผนที่ต้องการพิกัดของขั้วโลกที่เที่ยงตรงและไม่เปลี่ยนตำแหน่ง ขั้วโลกในการแผนที่ (cartographical poles หรือ cartographic poles) จึงเป็นตำแหน่งคงที่บนโลกหรือวัตถุหมุนอื่นที่ตำแหน่งโดยประมาณที่เป็นไปได้ของขั้วโลกที่มีการเปลี่ยนแปลงนั้น
สภาพอากาศ

ขั้วโลกเหนือ ขั้วโลกใต้ มีอากาศหนาวจัด เนื่องจากการโคจรของโลกรอบดวงอาทิตย์ รังสีมีความเข้มข้นต่ำ บริเวณขั้วโลกทั้ง 2 ข้าง ในช่วงฤดูหนาวมีอากาศหนาวจัด และน้ำก็จับจนแข็ง และยังมีลมพายุที่พัดพาหิมะมาตกอย่างหนัก เรียกกันว่า พายุหิมะ (Blizzards)
พืช

เนื่องจากมีอากาศหนาวเย็น จึงมีพันธุ์พืชไม่มากนัก พืชบางชนิดมีความทนทานสูง บางครั้งอาจจมใต้หิมะเป็นเวลานานนับปี กว่าจะมีโอกาสเจริญเติบโตได้อีกเมื่อฤดูร้อนมาถึง หญ้าและพืชที่ทนทาน เช่น มอส ไลเคน ตะไคร่น้ำ มักมีพุ่มเตี้ย
สัตว์

ในอาร์กติกมีสัตว์จำนวนหนึ่งอาศัยอยู่ตลอดปี แต่บางชนิดก็อยู่ในฤดูที่อบอุ่น สัตว์ขั้วโลกเหนือส่วนใหญ่ มีขนหนา เพื่อความอบอุ่น เช่น วอลรัส วัวมัสก์ หมีขั้วโลก
มหาสมุทรที่ล้อมรอบแอนตาร์กติก คือถิ่นที่อยู่ของสัตว์หลายชนิด แต่ไม่กี่ชนิดที่อาศัยที่แอนตาร์กติกตลอดทั้งปี เช่น วาฬ แมวน้ำ กุ้งฝอย (krill)
นก

นกเพนกวิน มีอาศัยเฉพาะขั้วโลกใต้ ไม่เคยปรากฏในขั้วโลกเหนือ ส่วนนกอื่น ๆ ส่วนมากอาศัยอยู่ในขั้วโลกเฉพาะช่วงหน้าร้อน เช่น นกเค้าแมวสีขาว
ดูเพิ่ม

ขั้วแม่เหล็ก
ขั้วของวัตถุทางดาราศาสตร์อื่น
ขึ้นทำเนียบจับตาย

| ขึ้นทำเนียบจับตาย |
| --- | --- |

กำกับ: แอนดรูว์ เดวิส
เขียนบท: รอย ฮิกกินส์ (ตัวละคร)  เดวิด โทฮี (เรื่องและบทภาพยนตร์)  เจบ สจ๊วต (บทภาพยนตร์)
อำนวยการสร้าง: อาร์โนลด์ โคเพลสัน
นักแสดงนำ: แฮร์ริสัน ฟอร์ด ทอมมี ลี โจนส์ เจอเรน เครบเบ โจ เพนโทลีอาโน จูลีแอนน์ มัวร์ เอล. สก๊อตต์ คาร์ลดเวลล์ นีล ฟลินน์
กำกับภาพ: ไมเคิล แชปแมน
ตัดต่อ: เดนนิส ไวเคอร์
ดนตรีประกอบ: เจมส์ นิวตัน โฮเวิร์ด
ผู้จัดจำหน่าย: วอร์เนอร์ บราเธอร์ส พิคเจอร์ส
วันฉาย: 6 สิงหาคม ค.ศ. 1993
ความยาว: 130 นาที
ภาษา: อังกฤษ
ทุนสร้าง: 44,000,000 ดอลลาร์สหรัฐ
ทำเงิน: 368,700,000 ดอลลาร์สหรัฐ
ต่อจากนี้: U.S. Marshals (ค.ศ. 1998)
ข้อมูลจาก All Movie Guide
ขึ้นทำเนียบจับตาย (อังกฤษ: The Fugitive) เป็นภาพยนตร์ฮอลลีวู้ดในปี ค.ศ. 1993 นำแสดงโดยแฮร์ริสัน ฟอร์ด, ทอมมี ลี โจนส์, เจอเรน เครบเบ กำกับโดย แอนดรูว์ เดวิส