โลโก้
ยูเนี่ยนพีเดีย
การสื่อสาร
ดาวน์โหลดได้จาก Google Play
ใหม่! ดาวน์โหลด ยูเนี่ยนพีเดีย บน Android ™ของคุณ!
ดาวน์โหลด
เร็วกว่าเบราว์เซอร์!
 

กราฟสองส่วน

ดัชนี กราฟสองส่วน

ในคณิตศาสตร์สาขาทฤษฎีกราฟ กราฟสองส่วน (bipartite graph) คือ กราฟที่เซตจุดยอดสามารถแบ่งได้เป็น 2 เซตที่ไม่มีส่วนร่วมกัน และจุดยอด 2 จุดใด ๆ ในเซตเดียวกัน จะไม่มีเส้นเชื่อมเชื่อมระหว่างกัน กราฟสองส่วนมีประโยชน์ในการแก้ปัญหาการจับคู่ (matching problems) เช่น ปัญหาการจัดงาน สมมติว่ามีคนอยู่ P คน และมีงานอยู่ J งาน ซึ่งแต่ละคนจะทำงานได้บางงานเท่านั้น เราจะแทนปัญหานี้ด้วยกราฟที่มีจุดยอด P + J จุด ถ้า p_i สามารถทำงาน j_i ได้ เราจะแทนด้วยเส้นเชื่อมเชื่อมระหว่าง p_i กับ j_i ทฤษฎีบทการสมรส (marriage theorem) นั้นใช้คุณสมบัติของกราฟเรื่อง การจับคู่สมบูรณ์ (perfect matchings).

9 ความสัมพันธ์: กราฟกราฟ (คณิตศาสตร์)กราฟสองส่วนบริบูรณ์ก็ต่อเมื่อจุดยอดทฤษฎีกราฟคณิตศาสตร์ต้นไม้ (ทฤษฎีกราฟ)เซตอิสระ

กราฟ

กราฟ อาจหมายถึง.

ใหม่!!: กราฟสองส่วนและกราฟ · ดูเพิ่มเติม »

กราฟ (คณิตศาสตร์)

วาดของกราฟระบุชื่อที่มีจุดยอด 6 จุด และเส้นเชื่อม 7 เส้น ในคณิตศาสตร์และวิทยาการคอมพิวเตอร์ กราฟ (Graph) ประกอบไปด้วยเซตของวัตถุที่เรียกว่าจุดยอด (vertex) ซึ่งเชื่อมต่อกันด้วยเส้นเชื่อม (edge) โดยทั่วไปแล้วเรามักวาดรูปแสดงกราฟโดยใช้จุด (แทนจุดยอด) เชื่อมกันด้วยเส้น (แทนเส้นเชื่อม) กราฟเป็นวัตถุพื้นฐานของการศึกษาในวิยุตคณิต หัวข้อทฤษฎีกราฟ เส้นเชื่อมอาจมีทิศทางหรือไม่ก็ได้ ตัวอย่างเช่น สมมุติให้จุดยอดแทนคนและเส้นเชื่อมแทนการจับมือกัน เส้นเชื่อมก็จะเป็นเส้นเชื่อมไม่มีทิศ เพราะการที่ A จับมือ B ก็แปลว่า B จับมือ A อย่างไรก็ตาม สมมุติถ้าจุดยอดแทนคนและเส้นเชื่อมแทนการรู้จัก เส้นเชื่อมก็ต้องเป็นเส้นเชื่อมมีทิศทาง เพราะ A รู้จัก B ไม่จำเป็นว่า B ต้องรู้จัก A หรือนั่นก็คือความสัมพันธ์การรู้จักไม่เป็นความสัมพันธ์สมมาตร จุดยอดอาจจะถูกเรียกว่าโหนด ปม หรือจุด ในขณะที่เส้นเชื่อมอาจถูกเรียกว่าเส้น คำว่า "กราฟ" ถูกใช้ครั้งแรกโดย J.J. Sylvester ในปี..

ใหม่!!: กราฟสองส่วนและกราฟ (คณิตศาสตร์) · ดูเพิ่มเติม »

กราฟสองส่วนบริบูรณ์

ในคณิตศาสตร์สาขาทฤษฎีกราฟ กราฟสองส่วนบริบูรณ์ (complete bipartite graph) คือ กราฟสองส่วนที่จุดยอดทุกจุดในเซตแรก เชื่อมโยงกับจุดยอดทุกจุดในเซตที่สอง.

ใหม่!!: กราฟสองส่วนและกราฟสองส่วนบริบูรณ์ · ดูเพิ่มเติม »

ก็ต่อเมื่อ

↔ ⇔ ≡ สัญลักษณ์ทางตรรกศาสตร์สำหรับแทนก็ต่อเมื่อ ในวิชาตรรกศาสตร์และวิชาที่เกี่ยวข้อง เช่น คณิตศาสตร์และปรัชญา ก็ต่อเมื่อเป็นตัวดำเนินการทางตรรกศาสตร์แบบเงื่อนไขสองทางระหว่างประพจน์ เพราะว่าก็ต่อเมื่อเป็นเงื่อนไขสองทาง ตัวเชื่อมนี้สามารถเปรียบเทียบกับเงื่อนไขเชิงตรรกศาสตร์มาตรฐาน ชื่อภาษาอังกฤษของตัวเชื่อมนี้คือ if and only if มาจาก "only if" ซึ่งเท่ากับ "ถ้...

ใหม่!!: กราฟสองส่วนและก็ต่อเมื่อ · ดูเพิ่มเติม »

จุดยอด

อด (vertex) อาจหมายถึง; คณิตศาสตร.

ใหม่!!: กราฟสองส่วนและจุดยอด · ดูเพิ่มเติม »

ทฤษฎีกราฟ

กราฟที่มีจุดยอด 6 จุด และเส้นเชื่อม 7 เส้น ทฤษฎีกราฟ (graph theory) เป็นหนึ่งในสาขาคณิตศาสตร์และวิทยาการคอมพิวเตอร์ ที่ศึกษาถึงคุณสมบัติต่าง ๆ ของกราฟ.

ใหม่!!: กราฟสองส่วนและทฤษฎีกราฟ · ดูเพิ่มเติม »

คณิตศาสตร์

ยูคลิด (กำลังถือคาลิเปอร์) นักคณิตศาสตร์ชาวกรีก ในสมัย 300 ปีก่อนคริสตกาล ภาพวาดของราฟาเอลในชื่อ ''โรงเรียนแห่งเอเธนส์''No likeness or description of Euclid's physical appearance made during his lifetime survived antiquity. Therefore, Euclid's depiction in works of art depends on the artist's imagination (see ''Euclid''). คณิตศาสตร์ เป็นศาสตร์ที่มุ่งค้นคว้าเกี่ยวกับ โครงสร้างนามธรรมที่ถูกกำหนดขึ้นผ่านทางกลุ่มของสัจพจน์ซึ่งมีการให้เหตุผลที่แน่นอนโดยใช้ตรรกศาสตร์สัญลักษณ์ และสัญกรณ์คณิตศาสตร์ เรามักนิยามโดยทั่วไปว่าคณิตศาสตร์เป็นสาขาวิชาที่ศึกษาเกี่ยวกับรูปแบบและโครงสร้าง, การเปลี่ยนแปลง และปริภูมิ กล่าวคร่าว ๆ ได้ว่าคณิตศาสตร์นั้นสนใจ "รูปร่างและจำนวน" เนื่องจากคณิตศาสตร์มิได้สร้างความรู้ผ่านกระบวนการทดลอง บางคนจึงไม่จัดว่าคณิตศาสตร์เป็นสาขาของวิทยาศาสตร์ ในอดีตผู้คนจะใช้สิ่งของแทนจำนวนที่จะนับยิ่งนานเข้าจำนวนประชากรยิ่งมีมากขึ้น ทำให้ผู้คนเริ่มคิดที่จะประดิษฐ์ตัวเลขขึ้นมาแทนการนับที่ใช้สิ่งของนับแทนจากนั้นก็มีการบวก ลบคูณ และหาร จากนั้นก็ก่อให้เกิดคณิตศาสตร์ คำว่า "คณิตศาสตร์" (คำอ่าน: คะ-นิด-ตะ-สาด) มาจากคำว่า คณิต (การนับ หรือ คำนวณ) และ ศาสตร์ (ความรู้ หรือ การศึกษา) ซึ่งรวมกันมีความหมายโดยทั่วไปว่า การศึกษาเกี่ยวกับการคำนวณ หรือ วิชาที่เกี่ยวกับการคำนวณ.

ใหม่!!: กราฟสองส่วนและคณิตศาสตร์ · ดูเพิ่มเติม »

ต้นไม้ (ทฤษฎีกราฟ)

กราฟที่เป็นต้นไม้ ต้นไม้ คือ กราฟที่สองจุดยอดใดๆจะมีวิถีเดินทางถึงกันได้เพียงวิถีเดียว หรือกล่าวอีกนัยหนึ่งว่า เป็นกราฟที่ไม่มีวัฏจักรแต่เป็นกราฟที่เชื่อมต่อกันหมด สำหรับกราฟที่ไม่เชื่อมต่อกันหมดเราเรียกว่า ป่า (forest).

ใหม่!!: กราฟสองส่วนและต้นไม้ (ทฤษฎีกราฟ) · ดูเพิ่มเติม »

เซตอิสระ

ซตอิสระ ในทฤษฎีกราฟ เซตอิสระของกราฟ G หมายถึงเซตของจุดที่คู่จุดใด ๆ ภายในเซตไม่มีเส้นเชื่อมถึงกันเลย หรืออาจจะพูดได้อีกแบบหนึ่งคือ เส้นเชื่อมใด ๆ ที่อยู่ในกราฟจะมีจุดปลายของเส้นเชื่อมอยู่ในเซตนี้ไม่เกินหนึ่ง.

ใหม่!!: กราฟสองส่วนและเซตอิสระ · ดูเพิ่มเติม »

ขาออกขาเข้า
Hey! เราอยู่ใน Facebook ตอนนี้! »