สารบัญ
20 ความสัมพันธ์: กราฟ (คณิตศาสตร์)กราฟบริบูรณ์กราฟสองส่วนกราฟสองส่วนบริบูรณ์กราฟเชิงระนาบระดับขั้นวิถี (ทฤษฎีกราฟ)อนันต์จำนวนธรรมชาติจุดยอดทฤษฎีกราฟคู่อันดับคู่ไม่อันดับต้นไม้ (ทฤษฎีกราฟ)ต้นไม้ (โครงสร้างข้อมูล)ต้นไม้แบบทอดข้ามต้นไม้แบบทอดข้ามน้อยสุดปัญหาวิถีสั้นสุดโครงสร้างข้อมูลเซตอิสระ
กราฟ (คณิตศาสตร์)
วาดของกราฟระบุชื่อที่มีจุดยอด 6 จุด และเส้นเชื่อม 7 เส้น ในคณิตศาสตร์และวิทยาการคอมพิวเตอร์ กราฟ (Graph) ประกอบไปด้วยเซตของวัตถุที่เรียกว่าจุดยอด (vertex) ซึ่งเชื่อมต่อกันด้วยเส้นเชื่อม (edge) โดยทั่วไปแล้วเรามักวาดรูปแสดงกราฟโดยใช้จุด (แทนจุดยอด) เชื่อมกันด้วยเส้น (แทนเส้นเชื่อม) กราฟเป็นวัตถุพื้นฐานของการศึกษาในวิยุตคณิต หัวข้อทฤษฎีกราฟ เส้นเชื่อมอาจมีทิศทางหรือไม่ก็ได้ ตัวอย่างเช่น สมมุติให้จุดยอดแทนคนและเส้นเชื่อมแทนการจับมือกัน เส้นเชื่อมก็จะเป็นเส้นเชื่อมไม่มีทิศ เพราะการที่ A จับมือ B ก็แปลว่า B จับมือ A อย่างไรก็ตาม สมมุติถ้าจุดยอดแทนคนและเส้นเชื่อมแทนการรู้จัก เส้นเชื่อมก็ต้องเป็นเส้นเชื่อมมีทิศทาง เพราะ A รู้จัก B ไม่จำเป็นว่า B ต้องรู้จัก A หรือนั่นก็คือความสัมพันธ์การรู้จักไม่เป็นความสัมพันธ์สมมาตร จุดยอดอาจจะถูกเรียกว่าโหนด ปม หรือจุด ในขณะที่เส้นเชื่อมอาจถูกเรียกว่าเส้น คำว่า "กราฟ" ถูกใช้ครั้งแรกโดย J.J.
ดู อภิธานศัพท์ทฤษฎีกราฟและกราฟ (คณิตศาสตร์)
กราฟบริบูรณ์
กราฟบริบูรณ์ (complete graph) เป็น กราฟ ที่ทุกคู่ของ จุดยอด ถูกเชื่อมต่อด้วย เส้นเชื่อม เป็น กราฟสม่ำเสมอ ที่มีระดับขั้น n-1 กราฟบริบูรณ์บนจุดยอด n จุด ใช้สัญลักษณ์ K_n, มี n จุดยอด, และ \frac เส้นเชื่อม ไดกราฟบริบูรณ์ (complete digraph) ก็เป็นลักษณะเดียวกับกราฟ ต่างกันที่เส้นเชื่อมแต่ละเส้น จะถูกแทนด้วยเป็นเส้นเชื่อมระบุทิศทาง 2 เส้น ในทิศทางตรงข้ามกัน.
ดู อภิธานศัพท์ทฤษฎีกราฟและกราฟบริบูรณ์
กราฟสองส่วน
ในคณิตศาสตร์สาขาทฤษฎีกราฟ กราฟสองส่วน (bipartite graph) คือ กราฟที่เซตจุดยอดสามารถแบ่งได้เป็น 2 เซตที่ไม่มีส่วนร่วมกัน และจุดยอด 2 จุดใด ๆ ในเซตเดียวกัน จะไม่มีเส้นเชื่อมเชื่อมระหว่างกัน กราฟสองส่วนมีประโยชน์ในการแก้ปัญหาการจับคู่ (matching problems) เช่น ปัญหาการจัดงาน สมมติว่ามีคนอยู่ P คน และมีงานอยู่ J งาน ซึ่งแต่ละคนจะทำงานได้บางงานเท่านั้น เราจะแทนปัญหานี้ด้วยกราฟที่มีจุดยอด P + J จุด ถ้า p_i สามารถทำงาน j_i ได้ เราจะแทนด้วยเส้นเชื่อมเชื่อมระหว่าง p_i กับ j_i ทฤษฎีบทการสมรส (marriage theorem) นั้นใช้คุณสมบัติของกราฟเรื่อง การจับคู่สมบูรณ์ (perfect matchings).
ดู อภิธานศัพท์ทฤษฎีกราฟและกราฟสองส่วน
กราฟสองส่วนบริบูรณ์
ในคณิตศาสตร์สาขาทฤษฎีกราฟ กราฟสองส่วนบริบูรณ์ (complete bipartite graph) คือ กราฟสองส่วนที่จุดยอดทุกจุดในเซตแรก เชื่อมโยงกับจุดยอดทุกจุดในเซตที่สอง.
ดู อภิธานศัพท์ทฤษฎีกราฟและกราฟสองส่วนบริบูรณ์
กราฟเชิงระนาบ
กราฟเชิงระนาบ (planar graph) ในทฤษฎีกราฟ คือกราฟที่สามารถวาดบนระนาบได้โดยไม่มีเส้นเชื่อมใดๆ ตัดกัน เช่น กราฟต่อไปนี้เป็นกราฟเชิงระนาบ ไฟล์:6n-graf.svg 200px (รูปที่สอง สามารถวาดให้ไม่มีเส้นเชื่อมตัดกันได้ โดยย้ายเส้นทแยงมุมเส้นหนึ่งออกไปข้างนอก) แต่กราฟสองรูปข้างล่างนี้ ไม่เป็นกราฟเชิงระนาบ ''K''5 ''K''3,3 เนื่องจากเป็นไปไม่ได้ที่จะวาดกราฟสองรูปนี้โดยไม่มีเส้นเชื่อมตัดกัน กราฟสองรูปนี้เป็นกราฟที่ไม่เป็นกราฟเชิงระนาบที่เล็กที่สุดด้ว.
ดู อภิธานศัพท์ทฤษฎีกราฟและกราฟเชิงระนาบ
ระดับขั้น
ในคณิตศาสตร์สาขาทฤษฎีกราฟ ระดับขั้น (degree) ของ จุดยอด v ใน กราฟ เป็นจำนวนของ เส้นเชื่อม ซึ่งต่อกับจุดยอด v (สำหรับเส้นเชื่อมที่เป็นห่วง ให้นับ 2 ครั้ง) ดีกรีของจุดยอด v เขียนแทนในทางคณิตศาสตร์ว่า \deg(v).
ดู อภิธานศัพท์ทฤษฎีกราฟและระดับขั้น
วิถี (ทฤษฎีกราฟ)
ในคณิตศาสตร์ วิถี (path) ในกราฟคือลำดับของจุดยอด ซึ่งจุดยอดแต่ละจุดจะมีเส้นเชื่อมเชื่อมจุดยอดในลำดับที่อยู่ติดกัน.
ดู อภิธานศัพท์ทฤษฎีกราฟและวิถี (ทฤษฎีกราฟ)
อนันต์
ัญลักษณ์อนันต์ในรูปแบบต่าง ๆ อนันต์ (infinity; ใช้สัญลักษณ์ ∞) เป็นแนวคิดในทางคณิตศาสตร์และปรัชญาที่อ้างถึงจำนวนที่ไม่มีขอบเขตหรือไม่มีที่สิ้นสุด ในประวัติศาสตร์ ผู้คนต่างพัฒนาแนวคิดต่าง ๆ เกี่ยวกับธรรมชาติของอนันต์ ในทางคณิตศาสตร์ มีการจำกัดความของคำว่าอนันต์ในทฤษฎีเซต ภาษาอังกฤษของอนันต์ที่ว่า Infinity มาจากคำในภาษาละติน infinitas ซึ่งแปลว่า "ไม่มีที่สิ้นสุด" ในทางคณิตศาสตร์ เนื้อหาที่เกี่ยวกับอนันต์จะถือว่าอนันต์เป็นตัวเลข เช่น ใช้ในการนับปริมาณ เป็นต้นว่า "จำนวนพจน์เป็นอนันต์" แต่อนันต์ไม่ใช่ตัวเลขชนิดเดียวกับจำนวนจริง เกออร์ก คันทอร์ นักคณิตศาสตร์ชาวเยอรมันได้จัดระเบียบแนวคิดที่เกี่ยวกับอนันต์และเซตอนันต์ในช่วงปลายศตวรรษที่ 19 ถึงต้นศตวรรษที่ 20 เขายังได้ค้นพบว่าอนันต์มีการนับปริมาณแตกต่างกัน แนวคิดดังกล่าวถูกเรียกว่าภาวะเชิงการนับ เช่น เซตของจำนวนเต็มเป็นเซตอนันต์ที่นับได้ แต่เซตของจำนวนจริงเป็นเซตอนันต์ที่นับไม่ได้.
ดู อภิธานศัพท์ทฤษฎีกราฟและอนันต์
จำนวนธรรมชาติ
ในทางคณิตศาสตร์ จำนวนธรรมชาติ อาจหมายถึง จำนวนเต็มบวก หรือ จำนวนนับ (1, 2, 3, 4,...) หรือ จำนวนเต็มไม่เป็นลบ (0, 1, 2, 3, 4,...) ความหมายแรกมีการใช้ในทฤษฎีจำนวน ส่วนแบบหลังได้ใช้งานใน ตรรกศาสตร์,เซตและวิทยาการคอมพิวเตอร์ ถุ จำนวนธรรมชาติมีการใช้งานหลักอยู่สองประการ กล่าวคือเราสามารถใช้จำนวนธรรมชาติในการนับ เช่น มีส้มอยู่ 3 ผลบนโต๊ะ หรือเราอาจใช้สำหรับการจัดอันดับ เช่น เมืองนี้เป็นเมืองที่มีขนาดใหญ่เป็นอันดับที่ 3 ในประเทศ เป็นต้น คุณสมบัติของจำนวนธรรมชาติที่เกี่ยวกับการหารลงตัว เช่นการกระจายของจำนวนเฉพาะ เป็นเนื้อหาในทฤษฎีจำนวน ปัญหาที่เกี่ยวกับการนับ เช่น ทฤษฎีแรมซี นั้นถูกศึกษาในคณิตศาสตร์เชิงการจั.
ดู อภิธานศัพท์ทฤษฎีกราฟและจำนวนธรรมชาติ
จุดยอด
อด (vertex) อาจหมายถึง; คณิตศาสตร.
ดู อภิธานศัพท์ทฤษฎีกราฟและจุดยอด
ทฤษฎีกราฟ
กราฟที่มีจุดยอด 6 จุด และเส้นเชื่อม 7 เส้น ทฤษฎีกราฟ (graph theory) เป็นหนึ่งในสาขาคณิตศาสตร์และวิทยาการคอมพิวเตอร์ ที่ศึกษาถึงคุณสมบัติต่าง ๆ ของกราฟ.
ดู อภิธานศัพท์ทฤษฎีกราฟและทฤษฎีกราฟ
คู่อันดับ
ในคณิตศาสตร์ คู่อันดับ (a, b) เป็นคู่ของวัตถุทางคณิตศาสตร์ โดย a เรียกว่า สมาชิกตัวหน้า และ b เรียกว่า สมาชิกตัวหลัง คู่อันดับอาจจะมองเป็นพิกัดก็ได้ สำหรับคู่อันดับนั้น อันดับมีความสำคัญ นั่นคือคู่อันดับ (a, b) แตกต่างจากคู่อันดับ (b, a) ยกเว้นกรณีที่ a.
ดู อภิธานศัพท์ทฤษฎีกราฟและคู่อันดับ
คู่ไม่อันดับ
ในคณิตศาสตร์ คู่ไม่อันดับ เป็นเซตในรูปของ นั่นก็คือเซตที่มีสมาชิก 2 ตัวคือ a และ b โดยที่สมาชิกทั้งสองไม่มีลำดับมาก่อนหลัง ทำให้.
ดู อภิธานศัพท์ทฤษฎีกราฟและคู่ไม่อันดับ
ต้นไม้ (ทฤษฎีกราฟ)
กราฟที่เป็นต้นไม้ ต้นไม้ คือ กราฟที่สองจุดยอดใดๆจะมีวิถีเดินทางถึงกันได้เพียงวิถีเดียว หรือกล่าวอีกนัยหนึ่งว่า เป็นกราฟที่ไม่มีวัฏจักรแต่เป็นกราฟที่เชื่อมต่อกันหมด สำหรับกราฟที่ไม่เชื่อมต่อกันหมดเราเรียกว่า ป่า (forest).
ดู อภิธานศัพท์ทฤษฎีกราฟและต้นไม้ (ทฤษฎีกราฟ)
ต้นไม้ (โครงสร้างข้อมูล)
ต้นไม้ เป็น แบบชนิดข้อมูลนามธรรม ประเภทหนึ่ง มีลักษณะการเรียงเป็นกิ่งก้านสาขาแตกแขนงออกไป จะไม่มีวงวน (loop) โยงในสมาชิกตัวต่างๆ โดยสมาชิกจะถูกเก็บไว้ในประเภทข้อมูลชนิดวัตถุ (Object) หรือโครงสร้าง (Structure) เรียกว่าปม (node) ซึ่งจะมีตัวแปรซึ่งเก็บตัวชี้ (Pointer) ไปยังปมอื่นๆได้ ต้นไม้ถูกใช้ในการจัดการข้อมูลที่เปรียบเทียบกันได้ (comparable) อย่างรวดเร็วเช่น ตัวเลข หรือ การเรียงลำดับความสำคัญของข้อมูล เช่น การคำนวณที่มีวงเล็บ เป็นอาท.
ดู อภิธานศัพท์ทฤษฎีกราฟและต้นไม้ (โครงสร้างข้อมูล)
ต้นไม้แบบทอดข้าม
ต้นไม้ทอดข้ามกราฟ ต้นไม้ทอดข้าม หรือ ต้นไม้แผ่ทั่ว หมายถึง กราฟย่อยซึ่งมีลักษณะเป็นต้นไม้และมีทุกจุดยอดของกราฟเป็นจุดยอดทุกจุดของต้นไม้ด้วย การหาต้นไม้ทอดข้ามในกราฟใดๆ โดยเฉพาะต้นไม้ทอดข้ามน้อยสุด เป็นปัญหาที่พบบ่อยในวิทยาการคอมพิวเตอร์รูปแบบหนึ่ง.
ดู อภิธานศัพท์ทฤษฎีกราฟและต้นไม้แบบทอดข้าม
ต้นไม้แบบทอดข้ามน้อยสุด
ตัวอย่างการเชื่อมต่อโหนดแต่ละโหนดเข้าหากันด้วยน้ำหนักรวมน้อยที่สุดวิธีหนึ่งจากกราฟถ่วงน้ำหนัก ต้นไม้แผ่ทั่วที่น้อยที่สุด คือ การเชื่อมต่อโหนดทุก ๆ โหนดในกราฟไม่มีทิศทางเข้าหากัน โดยแต่ละแขนของกราฟมีน้ำหนัก และเป้าหมายคือเชื่อมต่อด้วยน้ำหนักรวมน้อยที่สุด หมวดหมู่:ทฤษฎีกราฟ หมวดหมู่:ปัญหาฟังก์ชันพหุนาม หมวดหมู่:ต้นไม้ทอดข้าม.
ดู อภิธานศัพท์ทฤษฎีกราฟและต้นไม้แบบทอดข้ามน้อยสุด
ปัญหาวิถีสั้นสุด
วิถีสั้นสุดบนกราฟไม่ระบุทิศทางที่ไม่ถ่วงน้ำหนักระหว่างจุดยอด 6 กับ 1 คือ (6, 4, 5, 1) ในทฤษฎีกราฟ ปัญหาวิถีสั้นสุด (shortest path problem) เป็นปัญหาที่ต้องการหาวิถีสั้นสุดระหว่างจุดยอด 2 จุดภายในกราฟ กล่าวคือในวิถีสั้นสุดนั้น ผลรวมของน้ำหนักในเส้นเชื่อมแต่ละเส้นรวมกันแล้วน้อยที่สุดในบรรดาวิถีทั้งหมด ตัวอย่างปัญหานี้เช่นการหาวิธีเดินทางจากจุดหนึ่งไปอีกจุดหนึ่งในแผนที่ ในกรณีนี้ จุดยอดแทนด้วยสถานที่ต่างๆ ส่วนเส้นเชื่อมแทนด้วยถนนหรือเส้นทาง และน้ำหนักบนเส้นเชื่อมแทนด้วยเวลาในการเดินทางด้วยถนนหรือเส้นทางนั้น.
ดู อภิธานศัพท์ทฤษฎีกราฟและปัญหาวิถีสั้นสุด
โครงสร้างข้อมูล
ในสาขาวิทยาการคอมพิวเตอร์ โครงสร้างข้อมูล เป็นวิธีการจัดเก็บข้อมูลในคอมพิวเตอร์เพื่อให้สามารถใช้งานได้อย่างมีประสิทธิภาพ บ่อยครั้งที่การเลือกโครงสร้างข้อมูลที่เหมาะสมจะทำให้เราสามารถเลือกใช้ขั้นตอนวิธีที่มีประสิทธิภาพไปพร้อมกันได้ การเลือกโครงสร้างข้อมูลนั้นโดยส่วนใหญ่แล้วจะเริ่มต้นจากการเลือกแบบชนิดข้อมูลนามธรรม โครงสร้างข้อมูลที่ออกแบบเป็นอย่างดีจะสามารถรองรับการประมวลผลที่หนักหน่วงโดยใช้ทรัพยากรที่น้อยที่สุดเท่าที่จะเป็นไปได้ ทั้งในแง่ของเวลาและหน่วยความจำ โครงสร้างข้อมูลแต่ละแบบจะเหมาะสมกับงานที่แตกต่างกัน และโครงสร้างข้อมูลบางแบบก็ออกแบบมาสำหรับบางงานโดยเฉพาะ อย่างเช่น ต้นไม้แบบบีจะเหมาะสำหรับระบบงานฐานข้อมูล ในกระบวนการออกแบบโปรแกรมคอมพิวเตอร์ การเลือกโครงสร้างข้อมูลเป็นสิ่งสำคัญอันดับแรกที่ต้องคำนึงถึง ซึ่งจากการพัฒนาระบบงานใหญ่ๆได้แสดงให้เห็นว่า ความยากในการพัฒนาและประสิทธิภาพของระบบจะขึ้นอยู่กับโครงสร้างข้อมูลที่เลือกใช้อย่างมาก หลังจากตัดสินใจเลือกโครงสร้างข้อมูลที่จะใช้แล้วก็มักจะทราบถึงขั้นตอนวิธีที่ต้องใช้ได้ทันที แต่ในบางครั้งก็อาจจะกลับกัน คือ การประมวลผลที่สำคัญๆของโปรแกรมได้มีการใช้ขั้นตอนวิธีที่ต้องใช้โครงสร้างข้อมูลบางแบบโดยเฉพาะ จึงจะทำงานได้เต็มประสิทธิภาพ ถึงอย่างไรก็ตาม ไม่ว่าจะเลือกโครงสร้างข้อมูลด้วยวิธีการใด โครงสร้างข้อมูลที่เหมาะสมก็เป็นสิ่งที่สำคัญมากอยู่ดี แนวความคิดในเรื่องโครงสร้างข้อมูลนี้ส่งผล กับการพัฒนาวิธีการมาตรฐานต่างๆในการออกแบบและเขียนโปรแกรม หลายภาษาโปรแกรมนั้นได้พัฒนารวมเอาโครงสร้างข้อมูลนี้ไว้เป็นส่วนหนึ่งของระบบโปรแกรม เพื่อประโยชน์ในการใช้ซ้ำ.
ดู อภิธานศัพท์ทฤษฎีกราฟและโครงสร้างข้อมูล
เซตอิสระ
ซตอิสระ ในทฤษฎีกราฟ เซตอิสระของกราฟ G หมายถึงเซตของจุดที่คู่จุดใด ๆ ภายในเซตไม่มีเส้นเชื่อมถึงกันเลย หรืออาจจะพูดได้อีกแบบหนึ่งคือ เส้นเชื่อมใด ๆ ที่อยู่ในกราฟจะมีจุดปลายของเส้นเชื่อมอยู่ในเซตนี้ไม่เกินหนึ่ง.
ดู อภิธานศัพท์ทฤษฎีกราฟและเซตอิสระ
หรือที่รู้จักกันในชื่อ กราฟถ่วงน้ำหนัก