สารบัญ
38 ความสัมพันธ์: บทตั้งการจับมือกราฟกราฟ (แบบชนิดข้อมูลนามธรรม)กราฟบริบูรณ์กราฟระบุทิศทางกราฟสองส่วนกราฟหนาแน่นกราฟทรานสโพสกราฟของฟังก์ชันกราฟเชิงระนาบการค้นหาตามค่าดีสุดการค้นหาแบบจำกัดความลึกการค้นหาแบบทาบูกำหนดการพลวัตภาวะคู่หรือคี่ของ 0มิติระดับขั้นรายการประชิดวิถี (ทฤษฎีกราฟ)สะพานทั้งเจ็ดแห่งเมืองเคอนิจส์แบร์กส่วนประกอบที่เชื่อมกันแบบเข้มอภิธานศัพท์ทฤษฎีกราฟจำนวนแรมซีย์จุดยอด (ทฤษฎีกราฟ)ทฤษฎีกราฟขั้นตอนวิธีของคริสโตไฟด์ขั้นตอนวิธีของคาร์เกอร์ขั้นตอนวิธีของโบรุฟกาขั้นตอนวิธีของไดก์สตราขั้นตอนวิธีแบบสุ่มขั้นตอนวิธีโบรน-เคอร์โบสท์ความต่อเนื่อง (ทฤษฎีกราฟ)ต้นไม้ (ทฤษฎีกราฟ)ต้นไม้วิถีสั้นสุดต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิดปัญหาวิถีสั้นสุดไดกราฟเส้นโค้งคีลิง
บทตั้งการจับมือ
ในทฤษฎีกราฟ บทตั้งการจับมือกล่าวไว้ว่า สำหรับกราฟไม่ระบุทิศทางจำกัดใด ๆ จะมีจุดยอดที่มีระดับขั้น (ดีกรี) คี่เป็นจำนวนคู่เสมอ อาจกล่าวให้เห็นเป็นรูปธรรมได้ว่าในงานเลี้ยงที่มีการจับมือกันนั้น จะมีคนเป็นจำนวนคู่คนที่จับมือคนอื่นคี่ครั้งเสมอ สูตรผลรวมระดับขั้น เป็นสูตรที่เป็นพื้นฐานของบทตั้งการจับมือ กล่าวไว้ว่า สำหรับกราฟที่มีเซตจุดยอด V และเซตเส้นเชื่อม E หรือก็คือ ผลรวมของระดับขั้นของจุดยอดทั้งหมด จะเท่ากับจำนวนสองเท่าของจำนวนเส้นเชื่อม เลออนฮาร์ด ออยเลอร์ได้พิสูจน์ว่าทั้งบทตั้งการจับมือและสูตรผลรวมระดับขั้นเป็นจริงใน..
ดู กราฟ (คณิตศาสตร์)และบทตั้งการจับมือ
กราฟ
กราฟ อาจหมายถึง.
กราฟ (แบบชนิดข้อมูลนามธรรม)
กราฟที่มี 6 จุดยอด และ 7 เส้นเชื่อม ในสาขาวิชาวิทยาการคอมพิวเตอร์ กราฟเป็นโครงสร้างข้อมูลที่นำแนวคิดของกราฟทางคณิตศาสตร์และไฮเปอร์กราฟมาทำให้เกิดผล โครงสร้างข้อมูลแบบกราฟประกอบด้วยเซตสองชุด คือ เซตของจุดยอด (หรือปม) และ เส้นเชื่อม เช่นเดียวกันกับทางคณิตศาสตร์ เส้นเชื่อม(x,y) มีหมายความว่า เส้นเชื่อมจากจุดยอด x ไปยังจุดยอด y โครงสร้างข้อมูลแบบกราฟอาจให้ค่ากับเส้นเชื่อมโดยอาจจะให้ความหมายได้หลายอย่าง เช่น มูลค่า ความจุ ความยาว น้ำหนัก ฯลฯ.
ดู กราฟ (คณิตศาสตร์)และกราฟ (แบบชนิดข้อมูลนามธรรม)
กราฟบริบูรณ์
กราฟบริบูรณ์ (complete graph) เป็น กราฟ ที่ทุกคู่ของ จุดยอด ถูกเชื่อมต่อด้วย เส้นเชื่อม เป็น กราฟสม่ำเสมอ ที่มีระดับขั้น n-1 กราฟบริบูรณ์บนจุดยอด n จุด ใช้สัญลักษณ์ K_n, มี n จุดยอด, และ \frac เส้นเชื่อม ไดกราฟบริบูรณ์ (complete digraph) ก็เป็นลักษณะเดียวกับกราฟ ต่างกันที่เส้นเชื่อมแต่ละเส้น จะถูกแทนด้วยเป็นเส้นเชื่อมระบุทิศทาง 2 เส้น ในทิศทางตรงข้ามกัน.
ดู กราฟ (คณิตศาสตร์)และกราฟบริบูรณ์
กราฟระบุทิศทาง
กราฟระบุทิศทาง ในทฤษฎีกราฟ กราฟระบุทิศทาง หรือ ไดกราฟ คือกราฟซึ่งเส้นเชื่อมมีทิศ กล่าวคือกราฟ G.
ดู กราฟ (คณิตศาสตร์)และกราฟระบุทิศทาง
กราฟสองส่วน
ในคณิตศาสตร์สาขาทฤษฎีกราฟ กราฟสองส่วน (bipartite graph) คือ กราฟที่เซตจุดยอดสามารถแบ่งได้เป็น 2 เซตที่ไม่มีส่วนร่วมกัน และจุดยอด 2 จุดใด ๆ ในเซตเดียวกัน จะไม่มีเส้นเชื่อมเชื่อมระหว่างกัน กราฟสองส่วนมีประโยชน์ในการแก้ปัญหาการจับคู่ (matching problems) เช่น ปัญหาการจัดงาน สมมติว่ามีคนอยู่ P คน และมีงานอยู่ J งาน ซึ่งแต่ละคนจะทำงานได้บางงานเท่านั้น เราจะแทนปัญหานี้ด้วยกราฟที่มีจุดยอด P + J จุด ถ้า p_i สามารถทำงาน j_i ได้ เราจะแทนด้วยเส้นเชื่อมเชื่อมระหว่าง p_i กับ j_i ทฤษฎีบทการสมรส (marriage theorem) นั้นใช้คุณสมบัติของกราฟเรื่อง การจับคู่สมบูรณ์ (perfect matchings).
ดู กราฟ (คณิตศาสตร์)และกราฟสองส่วน
กราฟหนาแน่น
ในคณิตศาสตร์ กราฟหนาแน่น คือกราฟซึ่งมีจำนวนเส้นเชื่อมมาก (จำนวนเส้นเชื่อมใกล้เคียงกับจำนวนเส้นเชื่อมของกราฟบริบูรณ์) ในทางกลับกัน กราฟไม่หนาแน่น คือที่มีจำนวนเส้นเชื่อมน้อย สำหรับกราฟไม่ระบุทิศทาง ความหนาแน่นของกราฟหาได้จาก จำนวนเส้นเชื่อมที่มากที่สุดคือ ½ |V| (|V|−1) ดังนั้นความหนาแน่นของกราฟที่มากที่สุดคือ 1 (กราฟบริบูรณ์) และความหนาแน่นของกราฟที่น้อยที่สุดคือ 0.
ดู กราฟ (คณิตศาสตร์)และกราฟหนาแน่น
กราฟทรานสโพส
ในทฤษฎีกราฟ กราฟทรานสโพส (transpose graph หรือ converse graph หรือ reverse graph) ของกราฟระบุทิศทาง G คือกราฟระบุทิศทางที่มีจุดยอดเช่นเดียวกับ G แต่เส้นเชื่อมทั้งหมดได้ถูกกลับทิศทาง กล่าวคือ หากกราฟ G มีเส้นเชื่อม (u,v) แล้ว กราฟทราสโพสของ G จะมีเส้นเชื่อม (v,u) แทน.
ดู กราฟ (คณิตศาสตร์)และกราฟทรานสโพส
กราฟของฟังก์ชัน
1.
ดู กราฟ (คณิตศาสตร์)และกราฟของฟังก์ชัน
กราฟเชิงระนาบ
กราฟเชิงระนาบ (planar graph) ในทฤษฎีกราฟ คือกราฟที่สามารถวาดบนระนาบได้โดยไม่มีเส้นเชื่อมใดๆ ตัดกัน เช่น กราฟต่อไปนี้เป็นกราฟเชิงระนาบ ไฟล์:6n-graf.svg 200px (รูปที่สอง สามารถวาดให้ไม่มีเส้นเชื่อมตัดกันได้ โดยย้ายเส้นทแยงมุมเส้นหนึ่งออกไปข้างนอก) แต่กราฟสองรูปข้างล่างนี้ ไม่เป็นกราฟเชิงระนาบ ''K''5 ''K''3,3 เนื่องจากเป็นไปไม่ได้ที่จะวาดกราฟสองรูปนี้โดยไม่มีเส้นเชื่อมตัดกัน กราฟสองรูปนี้เป็นกราฟที่ไม่เป็นกราฟเชิงระนาบที่เล็กที่สุดด้ว.
ดู กราฟ (คณิตศาสตร์)และกราฟเชิงระนาบ
การค้นหาตามค่าดีสุด
การค้นแบบดีที่สุด (Best first search) คือขั้นตอนวิธีในการค้นหาในกราฟ เป็นการนำข้อดีของการค้นหาตามแนวกว้าง และการค้นหาตามแนวลึกมารวมกัน โดยการค้นหาแบบดีที่สุด จะเลือกจุดยอดที่มีค่าดีสุดซึ่งอาศัยฮิวริสติกฟังก์ชัน ในการหา ฮิวริสติกฟังก์ชัน ใช้หลักการของ ขั้นตอนวิธีแบบละโมบ เป็นการคาดเดาอย่างมีเหตุผลแต่อาจไม่ใช่คำตอบที่สมบูรณ์ โดยจะแปลงจากสถานะปัจจุบันไปเป็นตัวเลข ซึ่งตัวเลขนี้จะบ่งบอกว่าเข้าใกล้เป้าหมายมากน้อยเพียงใด ซึ่งฮิวริสติกฟังก์ชันจะช่วยบอกว่าควรไปในทิศทางใด ถ้าฟังก์ชันดีก็จะกระจายโหนดน้อยเข้าสู่เป้าหมายได้ไว ถ้าฟังก์ชันไม่ดีอาจค้นหาผิด ได้คำตอบที่ไม่ดีที่สุด หรือคำตอบผิดไปเลยก็ได้ โดยเฉลี่ยแล้วจะค้นหาได้ดีกว่าการค้นหาตามแนวกว้างและการค้นหาตามแนวลึก หรือก็คือ การค้นหาแบบดีที่สุดเป็นกระบวนการค้นหาข้อมูลที่ได้นำเอาข้อดีของทั้งการค้นหาตามแนวลึกและการค้นหาตามแนวกว้าง มารวมกันเป็นวิธีการเดียว โดยที่แต่ละขั้นของการค้นหาในโหนดลูกนั้น การค้นหาแบบดีที่ดีก่อนจะเลือกเอา โหนดที่ดีที่สุด (most promising) และการที่จะทราบว่าโหนดใดดีที่สุดนี้สามารถทำได้โดยอาศัยฮิวริสติกฟังก์ชัน ซึ่งฮิวริสติก ฟังก์ชันนี้จะทำหน้าที่เหมือนตัววัดผล และให้ผลของการวัดนี้ออกมาเป็นคะแนน.
ดู กราฟ (คณิตศาสตร์)และการค้นหาตามค่าดีสุด
การค้นหาแบบจำกัดความลึก
การค้นแบบจำกัดความลึก หรือ การค้นหาแบบจำกัดความลึก (depth limited search) เป็นขั้นตอนวิธีทางวิทยาการคอมพิวเตอร์ที่ใช้ในการหาปมบนกราฟซึ่งได้ปรับปรุงจากการค้นหาเชิงลึก (depth first search) เพื่อใช้ในงานค้นหากราฟ ที่ต้องการประสิทธิภาพสูงขึ้น โดยขั้นตอนวิธีนี้ เป็นพื้นฐานของ Iterative deepening depth-first search ซึ่งเป็นขั้นตอนวิธีสำหรับการค้นหาสถานะ (state space search) ที่อาศัยการค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึกไปเรื่อยๆ เพื่อหาคำตอบที่ดีที.
ดู กราฟ (คณิตศาสตร์)และการค้นหาแบบจำกัดความลึก
การค้นหาแบบทาบู
การค้นทาบู (tabu search) เป็นการค้นหาข้อมูลในคอมพิวเตอร์แบบวิธีโคจรตามเส้นกราฟ โดยการค้นทาบูมีลักษณะพิเศษคือมีเพิ่มประสิทธิภาพการค้นหาตามเส้นกราฟแบบเดิมด้วยการใช้โครงสร้างข้อมูลเพื่อจำปัญหาที่ได้แก้และทราบคำตอบที่ยอมรับได้แล้ว ไม่แก้ปัญหาเดิมซ้ำอีกครั้งหรือปัญหาที่ไม่ทางแก้ได้สำเร็จในเวลาที่จำกั.
ดู กราฟ (คณิตศาสตร์)และการค้นหาแบบทาบู
กำหนดการพลวัต
ในคณิตศาสตร์ วิทยาการคอมพิวเตอร์ และเศรษฐศาสตร์ กำหนดการพลวัต (dynamic programming) คือกระบวนการในการแก้ไขปัญหาที่ซับซ้อนโดยการแบ่งปัญหาให้เป็นปัญหาย่อยที่สามารถแก้ได้ง่ายกว่า คุณสมบัติพื้นฐานของปัญหาที่จะใช้กำหนดการพลวัตได้คือจะต้องมีปัญหาย่อยที่ทับซ้อนกัน (overlapping subproblem) และโครงสร้างย่อยที่เหมาะสมที่สุด (optimal substructure) ปัญหาที่ใช้กำหนดการพลวัตในการแก้ปัญหาจะใช้เวลาแก้รวดเร็วกว่าการแก้ปัญหาโดยตรงเป็นอย่างมาก หลักสำคัญของกำหนดการพลวัตมาจากการสังเกตว่าในการแก้ปัญหาที่ซับซ้อนนั้น จำเป็นที่จะต้องแก้ปัญหาที่เล็กกว่า (ปัญหาย่อย) และนำคำตอบของปัญหาย่อยเหล่านั้นมารวมกันเป็นคำตอบของปัญหาใหญ่ และในการดำเนินการแก้ปัญหาย่อยนี้ มีหลายปัญหาที่ปัญหาย่อยบางส่วนเหมือนกันทุกประการ ดังนั้นแทนที่จะแก้ไขปัญหาย่อยเหล่านี้ซ้ำอีกรอบ กระบวนการกำหนดการพลวัตจะใช้วิธีแก้ไขปัญหาย่อยเหล่านี้เพียงแค่ครั้งเดียว และเก็บคำตอบไว้ หรือที่เรียกว่าการจำ (memoization; ระวังสะกดเป็น memorization) เมื่อพบปัญหาย่อยดังกล่าวอีกครั้งก็ไม่จำเป็นต้องคำนวณซ้ำใหม่ แต่สามารถเรียกคำตอบที่เก็บไว้มาใช้ได้เลย กระบวนการนี้จะมีประสิทธิภาพดีเป็นอย่างยิ่งเมื่อปัญหาที่จะแก้มีจำนวนปัญหาย่อยที่ทับซ้อนกันเป็นจำนวนมาก ซึ่งหากไม่ได้ใช้กำหนดการพลวัตจะทำให้จำนวนครั้งในการแก้ปัญหาย่อยเติบโตแบบฟังก์ชันเลขชี้กำลัง ส่งผลให้เวลาในการแก้ไขปัญหาเพิ่มขึ้นเป็นอย่างมาก.
ดู กราฟ (คณิตศาสตร์)และกำหนดการพลวัต
ภาวะคู่หรือคี่ของ 0
ตราชั่งนี้มีวัตถุ 0 วัตถุ แบ่งเป็นสองข้างเท่ากัน 0 (ศูนย์) เป็นจำนวนคู่ กล่าวได้อีกอย่างคือ ภาวะคู่หรือคี่ของ 0 เป็นคู่ วิธีพิสูจน์ว่า 0 เป็นคู่ง่ายที่สุดคือตรวจสอบว่า 0 เข้ากับนิยามของ "คู่" หรือไม่ โดย 0 เป็นพหุคูณของ 2 คือ 0 × 2 ผลคือ ศูนย์มีคุณสมบัติทั้งหมดอันเป็นลักษณะของจำนวนคู่ ตัวอย่างเช่น 0 มีจำนวนคี่ที่มากกว่าและน้อยกว่าขนาบ, 0+x มีภาวะคู่หรือคี่เหมือน x และเซตของวัตถุ 0 วัตถุสามารถแบ่งได้เป็นสองเซตเท่า ๆ กัน 0 ยังเข้ากับแบบรูปที่จำนวนคู่อื่นมี กฎเลขคณิตภาวะคู่หรือคี่ เช่น คู่ − คู.
ดู กราฟ (คณิตศาสตร์)และภาวะคู่หรือคี่ของ 0
มิติ
มิติ ความหมายโดยทั่วไปหมายถึง สิ่งที่บอกคุณสมบัติของวัตถุ ได้แก่ ความกว้าง ความยาว และ ความสูง ส่วนในทางคณิตศาสตร์ มิติ หมายถึงจำนวนตัวเลขที่ต้องการเพื่อระบุตำแหน่งและคุณสมบัติของวัตถุใด ๆ ในปริภูมิ ในศาสตร์ต่าง ๆ อาจนิยามความหมายของคำว่า มิติ แทนจำนวนพารามิเตอร์ที่เกี่ยวข้อง เช่น ต้นทุน และ ราคา ในทางเศรษฐศาสตร์ ตัวอย่างในทางภูมิศาสตร์เช่น จุดบนพื้นผิวโลก สามารถกำหนดได้โดยตัวเลขค่าละติจูดและลองจิจูด ทำให้แผนที่ดังกล่าวมีสองมิติ (ถึงแม้ว่าโลกจะมีรูปร่างเกือบทรงกลมซึ่งมีสามมิติก็ตาม) ในการกำหนดตำแหน่งเครื่องบินหรืออากาศยานอื่น นอกจากละติจูดและลองจิจูดแล้ว ยังมีอีกตัวแปรหนึ่งคือค่า ความสูงจากพื้นดิน ทำให้พิกัดของเครื่องบิน เป็นสามมิติ เวลา สามารถใช้เป็นมิติที่สามหรือที่สี่ (เพิ่มจากพื้นที่สองหรือสามมิติเดิม) ในการกำหนดตำแหน่งได้.
ระดับขั้น
ในคณิตศาสตร์สาขาทฤษฎีกราฟ ระดับขั้น (degree) ของ จุดยอด v ใน กราฟ เป็นจำนวนของ เส้นเชื่อม ซึ่งต่อกับจุดยอด v (สำหรับเส้นเชื่อมที่เป็นห่วง ให้นับ 2 ครั้ง) ดีกรีของจุดยอด v เขียนแทนในทางคณิตศาสตร์ว่า \deg(v).
ดู กราฟ (คณิตศาสตร์)และระดับขั้น
รายการประชิด
รายการประชิด(อังกฤษ: Adjacency List) เป็นวิธีการของโครงสร้างแบบรายการของทฤษฎีกราฟ ซึ่งเป็นการใช้ลิสต์ในการเก็บข้อมูลของกราฟซึ่งเป็นโครงสร้างข้อมูลโดยวิธีการนี้จะใช้สำหรับการแก้ปัญหาของทฤษฎีกราฟ.
ดู กราฟ (คณิตศาสตร์)และรายการประชิด
วิถี (ทฤษฎีกราฟ)
ในคณิตศาสตร์ วิถี (path) ในกราฟคือลำดับของจุดยอด ซึ่งจุดยอดแต่ละจุดจะมีเส้นเชื่อมเชื่อมจุดยอดในลำดับที่อยู่ติดกัน.
ดู กราฟ (คณิตศาสตร์)และวิถี (ทฤษฎีกราฟ)
สะพานทั้งเจ็ดแห่งเมืองเคอนิจส์แบร์ก
แผนที่ของเมืองเคอนิจส์แบร์กนสมัยออยเลอร์ แสดงให้เห็นสะพานทั้งเจ็ด สะพานทั้งเจ็ดแห่งเมืองเคอนิจส์แบร์ก (Seven Bridges of Königsberg) เป็นปัญหาที่ได้รับแรงบันดาลใจมาจากสถานที่ คือ เมืองเคอนิจส์แบร์ก ในปรัสเซีย (คาลินินกราด รัสเซีย ในปัจจุบัน) ซึ่งตั้งอยู่บนแม่น้ำเพรเกิลและมีเกาะอยู่ 2 เกาะเชื่อมต่อถึงกันด้วยสะพานทั้ง 7 สะพาน คำถามคือ เป็นไปได้หรือไม่ที่จะเดินให้ครบทุกสะพาน โดยผ่านแต่ละสะพานเพียงครั้งเดียวและกลับมาที่จุดเริ่มต้นได้ ในพ.ศ.
ดู กราฟ (คณิตศาสตร์)และสะพานทั้งเจ็ดแห่งเมืองเคอนิจส์แบร์ก
ส่วนประกอบที่เชื่อมกันแบบเข้ม
กราฟแสดงส่วนประกอบที่เชื่อมกันแบบเข้ม โดยในกราฟมีทั้งหมด 3 ส่วน ส่วนประกอบที่เชื่อมกันแบบเข้ม (Strongly Connected Component: SCC) คือ กราฟที่เชื่อมกันแบบเข้ม (Strongly Connected Graph) ซึ่งเป็นกราฟย่อยที่ใหญ่ที่สุดในกราฟใหญ่ หรือ กราฟย่อยใหญ่ที่สุดที่เป็นการเชื่อมกันแบบเข้ม.
ดู กราฟ (คณิตศาสตร์)และส่วนประกอบที่เชื่อมกันแบบเข้ม
อภิธานศัพท์ทฤษฎีกราฟ
ทฤษฎีกราฟเติบโตอย่างรวดเร็วในวงการวิจัยด้านคณิตศาสตร์ และมีคำศัพท์เฉพาะทางอยู่หลายคำ บทความนี้จะรวบรวมคำและความหมายของศัพท์ในทฤษฎีกราฟ.
ดู กราฟ (คณิตศาสตร์)และอภิธานศัพท์ทฤษฎีกราฟ
จำนวนแรมซีย์
ำนวนแรมซีย์ R(m, n) ในคณิตศาสตร์เชิงการจัด หมายถึง จำนวนจุดยอดของกราฟสมบูรณ์ที่น้อยที่สุดที่เมื่อระบายสีเส้นเชื่อมด้วย 2 สีในวิธีใดๆ จะทำให้เกิดกราฟย่อยที่มีจุดยอด m จุด ซึ่งเส้นเชื่อมทุกเส้นมีสีที่ 1 หรือเกิดกราฟย่อยที่มีจุดยอด n จุด ซึ่งเส้นเชื่อมทุกเส้นมีสีที่ 2 จำนวนแรมซีย์สำหรับจำนวนที่มากกว่าสองจำนวนที่อยู่ในรูป (n1,..., nc) จะหมายถึงจำนวนจุดยอดของกราฟสมบูรณ์ที่น้อยที่สุดที่เมื่อระบายสีเส้นเชื่อมด้วย c สีในวิธีใดๆ จะมีค่า i อย่างน้อย 1 ค่า ที่มีค่าตั้งแต่ 1 ถึง n ที่ทำให้เกิดกราฟย่อยที่มีจุดยอด ni จุด ซึ่งเส้นเชื่อมทุกเส้นมีสีที่ i.
ดู กราฟ (คณิตศาสตร์)และจำนวนแรมซีย์
จุดยอด (ทฤษฎีกราฟ)
กราฟซึ่งมี 6 จุดยอดและ 7 เส้นเชื่อม และจุดยอดหมายเลข 6 เป็นจุดยอดปลาย ในทฤษฎีกราฟ จุดยอด หรือ โหนด เป็นส่วนประกอบอย่างหนึ่งที่ทำให้เกิดกราฟ กราฟไม่ระบุทิศทางประกอบด้วยเซตของจุดยอดและเซตของเส้นเชื่อม (คู่ไม่อันดับของจุดยอด) ในขณะที่กราฟระบุทิศทางประกอบด้วยเซตของจุดยอดและเซตของเส้นเชื่อมที่มีทิศทาง (คู่อันดับของจุดยอด) จุดยอด w เรียกว่าอยู่ ประชิด (adjacent) กับจุดยอด v โดยที่ v ไม่ใช่ w ก็ต่อเมื่อกราฟนั้นมีเส้นเชื่อม (v,w) และเพื่อนบ้านของจุดยอด v คือจุดยอดทั้งหมดที่ประชิดกับ v.
ดู กราฟ (คณิตศาสตร์)และจุดยอด (ทฤษฎีกราฟ)
ทฤษฎีกราฟ
กราฟที่มีจุดยอด 6 จุด และเส้นเชื่อม 7 เส้น ทฤษฎีกราฟ (graph theory) เป็นหนึ่งในสาขาคณิตศาสตร์และวิทยาการคอมพิวเตอร์ ที่ศึกษาถึงคุณสมบัติต่าง ๆ ของกราฟ.
ดู กราฟ (คณิตศาสตร์)และทฤษฎีกราฟ
ขั้นตอนวิธีของคริสโตไฟด์
ั้นตอนวิธีของคริสโตไฟด์ (Christofides algorithm) ตั้งชื่อตาม นิคอส คริสโตฟิลด์ เป็นขั้นตอนวิธีในการแก้ปัญหาบางกลุ่มของปัญหาการเดินทางของพนักงานขาย ที่มีเส้นเชื่อมถ่วงน้ำหนักเป็นไปตามความไม่เสมอภาคของสามเหลี่ยม ซึ่งได้คำตอบที่มีอัตราส่วนการประมาณ เป็น 1.5 เท่าของคำตอบดีที.
ดู กราฟ (คณิตศาสตร์)และขั้นตอนวิธีของคริสโตไฟด์
ขั้นตอนวิธีของคาร์เกอร์
ในวิทยาการคอมพิวเตอร์และทฤษฎีกราฟ ขั้นตอนวิธีของคาร์เกอร์ (Karger's algorithm) เป็น Monte Carlo method เพื่อคำนวณหา การตัดน้อยสุด (minimun cut) ของกราฟต่อเนื่อง ซึ่งถูกพัฒนาขึ้นโดย David Karger โดยการตัดน้อยสุด คือ จำนวนเส้นเชื่อมน้อยสุดที่ต้องลบออกเพื่อให้กราฟแยกเป็น 2 ส่วน(component).
ดู กราฟ (คณิตศาสตร์)และขั้นตอนวิธีของคาร์เกอร์
ขั้นตอนวิธีของโบรุฟกา
ั้นตอนวิธีโบรุฟกา (Borůvka's algorithm) คือขั้นตอนวิธีสำหรับหาต้นไม้ทอดข้ามน้อยที่สุดในกราฟที่ทุกเส้นเชื่อมมีน้ำหนักไม่เท่ากัน.
ดู กราฟ (คณิตศาสตร์)และขั้นตอนวิธีของโบรุฟกา
ขั้นตอนวิธีของไดก์สตรา
ั้นตอนวิธีของไดก์สตรา (Dijkstra's algorithm) ถูกคิดค้นขึ้นโดยนักวิทยาการคอมพิวเตอร์ชาวดัตช์นามว่า แอ็ดส์เคอร์ ไดก์สตรา (Edsger Dijkstra) ในปี 1959 เพื่อแก้ไขปัญหาวิถีสั้นสุดจากจุดหนึ่งใด ๆ สำหรับกราฟที่มีความยาวของเส้นเชื่อมไม่เป็นลบ สำหรับขั้นตอนวิธีนี้จะหาระยะทางสั้นที่สุดจากจุดหนึ่งไปยังจุดใด ๆ ในกราฟโดยจะหาเส้นทางที่สั้นที่สุดไปทีละจุดยอดเรื่อย ๆ จนครบตามที่ต้องการ.
ดู กราฟ (คณิตศาสตร์)และขั้นตอนวิธีของไดก์สตรา
ขั้นตอนวิธีแบบสุ่ม
ั้นตอนวิธีแบบสุ่ม (randomized algorithm) เป็นขั้นตอนวิธีที่ยอมให้มีการโยนเหรียญได้ ในทางปฏิบัติ เครื่องที่ใช้ทำงานขั้นตอนวิธีนี้ จะต้องใช้ตัวสร้างเลขสุ่มเทียม (pseudo-random number generator) ในการสร้างตัวเลขสุ่มขึ้นมา อัลกอรึทึมโดยทั่วๆไปมักใช้บิทสุ่ม (random bit) สำหรับเป็นอินพุตเสริม เพื่อชี้นำการกระทำของมันต่อไป โดยมีความหวังว่าจะช่วยให้มีประสิทธิภาพที่ดีใน "กรณีส่วนมาก (average case)" หรือหากพูดในทางคณิตศาสตร์ก็คือ ประสิทธิภาพของขั้นตอนวิธีมีค่าเท่ากับตัวแปรสุ่ม (random variable) ซึ่งคำนวณจากบิทสุ่ม โดยหวังว่าจะมีค่าคาดหมาย (expected value) ที่ดี กรณีที่แย่มากที่สุดมักจะมีโอกาสเกิดขึ้นน้อยมากจนแทบจะไม่ต้องสนใ.
ดู กราฟ (คณิตศาสตร์)และขั้นตอนวิธีแบบสุ่ม
ขั้นตอนวิธีโบรน-เคอร์โบสท์
ั้นตอนวิธีโบรน-เคอร์โบสท์ (Bron–Kerbosch algorithm.) เป็นขั้นตอนวิธีการหากลุ่มพรรคพวกที่ใหญ่ที่สุดในกราฟไม่ระบุทิศทาง (undirected graph) ซึ่งก็คือการระบุสับเซตทั้งหมดของจุดยอด (vertex) ประกอบด้วยคุณสมบัติสองประการคือ แต่ละคู่ของจุดยอดของสับเซตที่ถูกระบุแต่ละครั้งจะต้องถูกเชื่อมโดยเส้นเชื่อมเสมอและ ไม่มีสับเซตใดที่จะมีจุดยอดเพิ่มเติมถูกเพิ่มเข้าไปในสับเซตขณะที่มันเป็นการเชื่อมต่อที่บริบูรณ์ (complete connectivity) ขั้นตอนวิธีโบรน-เคอร์โบสท์ ถูกออกแบบโดย แยป เคอร์โบสท์ และ แคนรีด โบรน สองนักวิทยาศาสตร์ชาวดัตช์ ซึ่งตีพิมพ์เรื่องนี้ในปี ค.ศ.1973 แม้ว่าขั้นตอนวิธีอื่นๆ สำหรับการแก้ปัญหากลุ่มพรรคพวก (clique problem) จะมีเวลาการทำงานดีกว่าในทางทฤษฎีสำหรับข้อมูลขาเข้าที่เป็นเซตอิสระขนาดใหญ่สุด (maximal independent set) จำนวนน้อยๆ แต่ขั้นตอนวิธีโบรน-เคอร์โบสท์ และการปรับปรุงจากขั้นตอนวิธีนี้ถูกรายงานบ่อยครั้งว่ามีประสิทธิภาพดีกว่าแบบอื่นๆ ในทางปฏิบัติ ขั้นตอนวิธีนี้มีชื่อเสียงและถูกนำไปใช้อย่างกว้างขวางในการใช้งานที่ต้องใช้ขั้นตอนวิธีเกี่ยวกับกราฟ เช่น เคมีการคำนวณ (computational chemistry) ขั้นตอนวิธีที่เกิดขึ้นในช่วงเดียวกันของอัคโคยันลู (Akkoyunlu) ในปี..1973 ซึ่งแม้ว่าอาจจะถูกนำเสนอในรูปแบบที่ต่างออกไป แต่ก็จะมีลักษณะที่เหมือนกับขั้นตอนวิธีโบรน-เคอร์โบสท์ เมื่อถูกสร้างเป็นต้นไม้ค้นหาแบบเวียนเกิดที่เหมือนกัน.
ดู กราฟ (คณิตศาสตร์)และขั้นตอนวิธีโบรน-เคอร์โบสท์
ความต่อเนื่อง (ทฤษฎีกราฟ)
ในคณิตศาสตร์และวิทยาการคอมพิวเตอร์ เรื่องทฤษฎีกราฟ ความต่อเนื่อง หรือ ความเชื่อมโยง (Connectivity) เป็นคุณสมบัติหนึ่งของกราฟ โดยกราฟต่อเนื่อง หรือ กราฟเชื่อมโยง (Connected graph) หมายความว่ากราฟไม่ขาดจากกัน กล่าวคือ สำหรับทุกๆสองจุดยอดใดๆ จะสามารถไปถึงกันได้ หรือก็คือมีวิถีระหว่างจุดยอดทั้งสอง ในขณะที่กราฟไม่ต่อเนื่อง หรือ กราฟไม่เชื่อมโยง (Unconnected graph) หมายความว่ากราฟนั้นขาดออกจากกัน กล่าวคือมีอย่างน้อยสองจุดยอด ที่ไม่สามารถไปถึงกันได้ หรือก็คือไม่มีวิถีระหว่างจุดยอดทั้งสองจุดนั้น ความต่อเนื่องของกราฟ ยังสามารถมองได้ในอีกแง่มุมหนึ่ง คือจำนวนของจุดยอดหรือเส้นเชื่อมที่น้อยที่สุด ที่ถ้าลบจุดยอดหรือเส้นเชื่อมเหล่านั้นทิ้งแล้ว กราฟดังกล่าวจะกลายเป็นกราฟไม่ต่อเนื่องDiestel, R.,, 2005, p 12.
ดู กราฟ (คณิตศาสตร์)และความต่อเนื่อง (ทฤษฎีกราฟ)
ต้นไม้ (ทฤษฎีกราฟ)
กราฟที่เป็นต้นไม้ ต้นไม้ คือ กราฟที่สองจุดยอดใดๆจะมีวิถีเดินทางถึงกันได้เพียงวิถีเดียว หรือกล่าวอีกนัยหนึ่งว่า เป็นกราฟที่ไม่มีวัฏจักรแต่เป็นกราฟที่เชื่อมต่อกันหมด สำหรับกราฟที่ไม่เชื่อมต่อกันหมดเราเรียกว่า ป่า (forest).
ดู กราฟ (คณิตศาสตร์)และต้นไม้ (ทฤษฎีกราฟ)
ต้นไม้วิถีสั้นสุด
ในทฤษฎีกราฟ ต้นไม้วิถีสั้นสุด เป็นต้นไม้ที่ได้จากการแก้ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวบนกราฟที่กำหนดให้ โดยต้นไม้นี้จะเป็นกราฟย่อยของกราฟนั้นและระยะทางระหว่างรากกับจุดยอดใด ๆ มีค่าน้อยที่สุด การที่แก้ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวแล้วได้ต้นไม้นั้นเพราะว่าหากมีสองวิถีระหว่างรากกับโหนด v (มีวัฏจักร) เราสามารถเลือกใช้วิถีที่สั้นกว่า และลบเส้นเชื่อมที่มีระยะทางของวิถีที่ยาวกว่าได้โดยไม่ทำให้ระยะทางจากรากไปโหนดใดๆเพิ่มขึ้น หากโหนดทุกๆคู่ในกราฟที่กำหนดให้มีวิถีสั้นสุดเพียงแบบเดียว จะได้ว่าต้นไม้วิถีสั้นสุดก็จะมีเพียงแบบเดียวด้วยเช่นกัน ในกราฟที่ไม่มีน้ำหนักติดลบ ขั้นตอนวิธีของไดค์สตรา สามารถคำนวณหาต้นไม้วิถีสั้นสุดได้ สำหรับกราฟที่มีน้ำหนักติดลบ สามารถใช้ ขั้นตอนวิธีของเบลแมน-ฟอร์ด แทนได้ ดี.
ดู กราฟ (คณิตศาสตร์)และต้นไม้วิถีสั้นสุด
ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิด
ต้นไม้แบบทอดข้ามเล็กสุดของยูคลิด ที่มีจุด 25 จุด ในระนาบ ต้นไม้ทอดข้ามที่น้อยที่สุดแบบยุคลิด หรือ ต้นไม้แผ่ทั่วที่น้อยที่สุดแบบยุคลิด (Euclidean minimum spanning tree) เป็นปัญหาทางทฤษฎีกราฟเกี่ยวกับการหาต้นไม้ทอดข้ามที่น้อยที่สุดบนระนาบแบบยูคลิด หรือก็คือวิธีเชื่อมโยงจุดต่าง ๆ บนระนาบสองมิติ ให้เป็นต้นไม้และมีระยะทางรวมระหว่างจุดต่าง ๆ น้อยที่สุด โดยมองจุดต่าง ๆ เป็นจุดยอดและ ระยะทางระหว่างจุดยอดเป็นเส้นเชื่อม.
ดู กราฟ (คณิตศาสตร์)และต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิด
ปัญหาวิถีสั้นสุด
วิถีสั้นสุดบนกราฟไม่ระบุทิศทางที่ไม่ถ่วงน้ำหนักระหว่างจุดยอด 6 กับ 1 คือ (6, 4, 5, 1) ในทฤษฎีกราฟ ปัญหาวิถีสั้นสุด (shortest path problem) เป็นปัญหาที่ต้องการหาวิถีสั้นสุดระหว่างจุดยอด 2 จุดภายในกราฟ กล่าวคือในวิถีสั้นสุดนั้น ผลรวมของน้ำหนักในเส้นเชื่อมแต่ละเส้นรวมกันแล้วน้อยที่สุดในบรรดาวิถีทั้งหมด ตัวอย่างปัญหานี้เช่นการหาวิธีเดินทางจากจุดหนึ่งไปอีกจุดหนึ่งในแผนที่ ในกรณีนี้ จุดยอดแทนด้วยสถานที่ต่างๆ ส่วนเส้นเชื่อมแทนด้วยถนนหรือเส้นทาง และน้ำหนักบนเส้นเชื่อมแทนด้วยเวลาในการเดินทางด้วยถนนหรือเส้นทางนั้น.
ดู กราฟ (คณิตศาสตร์)และปัญหาวิถีสั้นสุด
ไดกราฟ
กราฟ อาจหมายถึง.
เส้นโค้งคีลิง
้นโค้งคีลิง ความเข้มข้นของคาร์บอนไดออกไซด์ในบรรยากาศซึ่งวัดที่หอดูดาวเมานาลัว เส้นโค้งคีลิง (Keeling Curve) เป็นกราฟซึ่งลงจุดการเปลี่ยนแปลงความเข้มข้นของคาร์บอนไดออกไซด์ในบรรยากาศของโลกอย่างต่อเนื่องตั้งแต่ปี 2501 กราฟนี้อาศัยการวัดอย่างต่อเนื่อง ณ หอดูดาวเมานาลัวในรัฐฮาวาย ภายใต้การกำกับดูแลของชาลส์ เดวิด คีลิง การวัดของคีลิงแสดงหลักฐานสำคัญว่าระดับคาร์บอนไดออกไซด์ในบรรยากาศกำลังเพิ่มขึ้นอย่างรวดเร็วเป็นชิ้นแรก นักวิทยาศาสตร์จำนวนมากยกย่องกราฟของคีลิงว่าเป็นผู้แรกที่ทำให้โลกสนใจการเพิ่มขึ้นของคาร์บอนไดออกไซด์ในบรรยากาศปัจจุบัน ชาลส์ เดวิด คีลิง แห่งสถาบันสมุทรศาสตร์สคริปปส์ ที่มหาวิทยาลัยแคลิฟอร์เนีย ซานดิเอโก เป็นบุคคลแรกที่วัดความเข้มข้นของคาร์บอนไดออกไซด์ในบรรยากาศเป็นประจำบ่อยครั้ง โดยอ่านค่าที่ขั้วโลกใต้และในรัฐฮาวายมาตั้งแต่ปี 2501 ก่อนหน้าคีลิง ความเข้มข้นของคาร์บอนไดออกไซด์ในบรรยากาศคาดกันว่าถูกกระทบจากความผันแปรคงที่ คีลิงพัฒนาเทคนิคการวัดให้สมบูรณ์และสังเกต "พฤติกรรมประจำวันอย่างเข้ม ด้วยค่าคงที่ราว 310 พีพีเอ็ม ในช่วงบ่าย" ณ ที่สามแห่ง คือ บิกซูร์ใกล้กับมอนเทอร์เรย์ ป่าฝนแห่งคาบสมุทรโอลิมปิกและป่าภูเขาสูงในรัฐแอริโซนา โดยการวัดอัตราส่วนของคาร์บอนสองไอโซโทป คีลิงให้เหตุผลว่าการเปลี่ยนแปลงประจำวันมาจากการหายใจจากพืชท้องถิ่นและดิน โดยค่าช่วงบ่ายเป็นตัวแทนของ "บรรยากาศอิสระ" เมื่อปี 2503 คีลิงและคณะระบุว่าบันทึกการวัดจากรัฐแคลิฟอร์เนีย แอนตาร์กติกาและรัฐฮาวายยาวพอที่จะเห็นการเพิ่มขึ้นปีต่อปีซึ่งสอดคล้องหยาบ ๆ กับปริมาณเชื้อเพลิงซากดึกดำบรรพ์ที่สันดาปในแต่ละปี ไม่เพียงแต่ความผันแปรประจำวันและฤดูกาล ในบทความอันทำให้เขามีชื่อเสียง คีลิงสังเกตว่า "ที่ขั้วโลกใต้ อัตราการเพิ่มขึ้นที่สังเกตได้นั้นใกล้เคียงกับที่คาดจากการสันดาปเชื้อเพลิงซากดึกดำบรรพ์" เขายังสังเกตว่า คาร์บอนไดออกไซด์ในบรรยากาศไม่ลดลงเนื่องจากการดูดซับจากมหาสมุทรอย่างชัดเจนด้ว.
ดู กราฟ (คณิตศาสตร์)และเส้นโค้งคีลิง
หรือที่รู้จักกันในชื่อ กราฟอย่างง่ายกราฟไม่ระบุทิศทางไดกราฟ (คณิตศาสตร์)เส้นเชื่อมเส้นเชื่อม (ทฤษฎีกราฟ)