กราฟ

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

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

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

เพื่อความสะดวกในการกล่าวข้อความในตอนต่อ ๆ ไป เราจะเรียกกราฟใด ๆ ที่เราอาจเริ่มต้นจากจุดใดจุดหนึ่ง ลากทับรอยเส้นของมันไปเรื่อย ๆ ให้ครบทุกเส้น เส้นละครั้งเดียว แล้วในที่สุดกลับมาบรรจบที่จุดเดิมนี้ว่า กราฟที่ลากได้

ขอให้สังเกตว่า ในกราฟแต่ละรูปที่เราลากได้นั้น จำนวนเส้นที่เราลากเข้าหาจุดใด ๆ ต้องเป็นจำนวนคู่เสมอ ดังนั้นกราฟที่ลากได้แต่ละรูปจำต้องมีจำนวนของเส้นที่พบกันที่แต่ละจุดเป็นจำนวนคู่ หากกราฟใดมีจุดสักจุดหนึ่ง หรือ หลาย ๆ จุด ซึ่งเป็นที่พบกันของเส้นต่าง ๆ ที่มีจำนวนเส้นเป็นเลขคี่ กราฟนั้นย่อมไม่เป็นกราฟที่ลากได้

เนื่องจากในกราฟแสดงสะพานตามปัญหาข้างต้น จุดต่าง ๆ เป็นที่พบกันของเส้น ๓ เส้นบ้าง ๕ เส้นบ้าง กราฟนี้จึงไม่ใช่กราฟที่ลากได้ ดังนั้นคำตอบของปัญหาการเดินข้ามสะพานข้างต้นก็คือ เราจะเดินข้ามสะพานตามเงื่อนไขดังกล่าวไม่ได้

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

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

เราจะพบว่ากราฟแสดงการเชื่อมโยงแผ่นดินทั้งสี่ด้วยสะพาน เป็นกราฟซึ่งแต่ละ จุดมีดีกรีที่ 2 แต่กราฟนี้ มิได้เป็นรูปที่ติดต่อเป็นชิ้นเดียวกัน จึงไม่เป็นกราฟที่ลากได้ ดังนั้นคุณสมบัติอีกอย่างหนึ่ง ซึ่งกราฟที่ลากได้จะต้องมีเสมอไปก็คือ การ มีลักษณะติดต่อเป็นชิ้นเดียว

ทฤษฎีบทว่าด้วยกราฟที่ลากได้ ซึ่งออยเลอร์พิสูจน์ไว้กล่าวว่า กราฟรูปหนึ่งรูปใดจะเป็นกราฟที่ลากได้ ก็ต่อเมื่อกราฟนั้นติดต่อเป็นชิ้นเดียว และ จุดทุกจุดมีดีกรีคู่เท่านั้น ปัจจุบันนี้เราเรียกกราฟเช่นนี้ว่า กราฟแบบออยเลอเรียน (Eulerien)

ปัญหาเกี่ยวกับการลากทับเส้นกราฟอีกประเภทหนึ่ง ซึ่งคล้ายกับปัญหาข้างต้น ปัญหาประเภทนี้มีว่า เราจะลากทับรอยเส้นกราฟไปเรื่อย ๆ โดยให้ผ่านจุดต่าง ๆ ของกราฟนั้นทุกจุด จุดละครั้งเดียว แล้วในที่สุดกลับมาบรรจบที่จุดเดิมได้ หรือ ไม่ ถ้าเราลองพิจารณากราฟในรูป ก. ข. ค. ในตัวอย่างข้างต้น เราจะพบว่ากราฟ รูป ก. กับ ค. นั้นเราทำได้ ส่วนกราฟรูป ข. นั้น เราจะลากไม่ได้ วิธีลากทับรอยกราฟ รูป ค. ให้ผ่านทุกจุด จุดละครั้งเดียว และ กลับมาถึงจุดเดิมนั้นเราอาจทำได้ตามวิธีใดวิธีหนึ่ง ดังแสดงในรูปต่อไปนี้

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

สาเหตุที่ทำให้เราลากให้ผ่านทุกจุดของกราฟ ข. จุดละครั้งเดียวไม่ได้ก็คือจุด ๆ หนึ่ง ในกราฟรูปนี้ มีคุณสมบัติพิเศษบางประการ

ในรูปกราฟ ข. นี้ หากเราลบจุดหมายเลข ๓ และ ลบทุกเส้นที่ต่อกับจุดนี้ออกเสีย เราจะได้กราฟที่เป็นสองส่วนแยกจากกัน เราเรียกจุด เช่นนี้ว่า จุดตัด จุดตัดจึงเป็นทางผ่านเพียงทางเดียว ที่เชื่อมต่อกราฟสองชิ้น ถ้าเริ่มต้นจากจากจุดใดจุดหนึ่ง แล้วลากให้ผ่านทุก ๆ จุด ในกราฟ เราย่อมต้องลากผ่านจุดตัดถึงสองครั้งเป็นอย่างหนึ่ง เราจึงสรุปได้ว่า กราฟที่มีจุดตัดย่อม ไม่เป็นกราฟแบบแฮมิลโทเนียน

บทกลับของข้อสรุปนี้ไม่เป็นจริง กล่าวคือ กราฟที่ไม่มีจุดตัดเลย แต่ไม่เป็นกราฟแบบแฮมิลโทเนียนก็มี รูปต่อไปนี้เป็นกราฟเช่นนั้น

นักคณิตศาสตร์ยุคปัจจุบัน ได้พยายามค้นหาเงื่อนไขที่สะดวกต่อการใช้เป็นเกณฑ์พิจารณาว่า กราฟรูปใดรูปหนึ่งเป็นกราฟแบบแฮมิลโทเนียน หรือ ไม่ แต่ก็ยังไม่มีผู้ใดค้นพบเงื่อนไขที่ดีเท่าเทียมกับเงื่อนไข ที่ใช้ในการพิจารณาว่า กราฟเป็นแบบออยเลอเรียน หรือ ไม่ เช่น มีผู้พบว่า กราฟใด ๆ ที่มีสามจุดขึ้นไป และ ติดต่อกันเป็นชิ้นเดียว ถ้าผลรวมของดีกรีของจุดที่ไม่ได้อยู่ติดกันแต่ละคู่ ไม่น้อยกว่าจำนวนจุดทั้งหมดในกราฟนั้น กราฟนั้นย่อมเป็นแบบแฮมิลโทเนียน ส่วนที่ยังไม่ค่อยจะดีนักของทฤษฎีบทนี้ ก็คือ เราไม่สามารถใช้ทฤษฎีบทนี้เพียงบทเดียว ตรวจสอบว่า กราฟเป็นแบบแฮมิลโทนเนียน หรือ ไม่ ได้ทุกรูป เพราะกราฟแบบแฮมิลโทเนียนบางรูป ที่ไม่เป็นไปตามเงื่อนไขของทฤษฎีบทนี้ก็มี เช่น รูปทางซ้ายมือ เป็นกราฟแบบแฮมิลโทเนียน ซึ่งจุดคู่ที่ห่างกันมีดีกรีรวมกันได้น้อยกว่าจำนวนของจุดในรูป

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

ในกราฟรูปที่สองนี้ ขอให้คิดเสียว่า เป็นกราฟซึ่งสร้างขึ้นในสามมิติ เส้นซึ่งโยง ก กับ ค และ ข กับ ง นั้นมิได้ตัดกัน แต่ข้าม และ ลอดซึ่งกัน และ กันดังเช่นสะพานกับแม่น้ำ อย่างไรก็ตาม ในการศึกษาเกี่ยวกับกราฟ เราศึกษาโดยการเขียนรูปลงบนแผ่นกระดาษ หรือ แผ่นอย่างอื่น ดังนั้นบางครั้งเราอาจจำยอมเขียนให้เส้นกราฟตัดกัน แต่ไม่นับว่า จุดตัดกันของเส้นกราฟเป็นจุดของกราฟของเรา

กราฟทั้งสองนี้มีรูปต่างกัน ทั้ง ๆ ที่แต่ละรูปแสดงถึงสิ่งเดียวกัน อาจกล่าวได้ว่า กราฟสองรูปนี้ต่างกันแต่เพียงรูปเท่านั้น โดยสาระอันแท้จริงแล้ว กราฟทั้งสองนี้เหมือนกัน ในกรณีเช่นนี้เราจะกล่าวว่า กราฟทั้งสองเป็นเสมือนกราฟเดียวกัน ต่อไปนี้เป็นตัวอย่างของกราฟ ซึ่งเป็นเสมือนกราฟเดียวกัน

การสร้างกราฟในสามมิติ โดยไม่ให้เส้นกราฟตัดกันนั้นเราทำได้เสมอ แต่ ถ้าจะจำกัดการเขียนให้เส้นกราฟทุกเส้นอยู่บนพื้นราบ เราอาจทำได้สำหรับบางรูป และอาจทำไม่ได้สำหรับบางรูปก็ได้ กราฟแสดงการรู้จักของคนห้าคนในตัวอย่าง ข้างต้น เป็นตัวอย่างของกราฟ ซึ่งเราอาจเขียนลงบนพื้นราบ โดยมิให้เส้นกราฟตัดกันเองเลยได้ โดยทั่ว ๆ ไปถ้ากราฟใดเป็นเสมือนกราฟเดียวกันกับกราฟรูปใดรูปหนึ่งบนพื้นราบซึ่งไม่มีเส้นคู่ใดตัดกันเลย เราจะกล่าวว่ากราฟนั้นเป็นกราฟที่เขียน ได้บนพื้นราบ ดังนั้นกราฟแสดงการรู้จักกันของคนทั้งห้าในตัวอย่างข้างต้นจึงเป็น กราฟที่เขียนได้บนพื้นราบ แต่ถ้าเราสมมุติเสียใหม่ว่าคนทั้งห้าต่างก็รู้จักกันทุกคู่ กราฟแสดงการรู้จักย่อมเป็นดังนี้

ถ้าเราเขียนรูปของกราฟนี้เสียใหม่ โดยพยายามไม่ให้เส้นกราฟตัดกันเองอย่างดีที่สุด เราคงได้รูปทำนองต่อไปนี้

แต่จะมีเส้นกราฟคู่หนึ่งตัดกันเอง ซึ่งเป็นความจริงที่อาจพิสูจน์ได้สำหรับกราฟรูปนี้ ส่วนกราฟบางรูป เราอาจต้องยอมให้เส้นกราฟตัดกันเองมากกว่าคู่เดียวก็เป็นได้ เราเรียกจำนวนน้อยสุดที่เราจำต้องยอมให้เส้นกราฟตัดกันเอง เมื่อเราเขียนบนพื้นราบว่า จำนวนทางข้ามของกราฟนั้น กราฟแสดงการรู้จักกันของคนห้าคนที่ต่างก็รู้จักกัน จึงเป็นกราฟที่มีจำนวนทางข้ามเป็น ๑ ของกราฟใด ๆ ที่เขียนได้บนพื้นราบ ก็คือกราฟที่มีจำนวนทางข้ามเป็น ๐
ปัญหาที่ได้รับความสนใจอย่างมากจากบรรดานักคิดค้นเกี่ยวกับเรื่องกราฟอีกเรื่องหนึ่งก็คือ ปัญหาเกี่ยวกับการพยายามระบายสีจุดของกราฟ ให้จุดที่อยู่ติดกันมีสีต่างกัน โดยพยายามใช้สีต่าง ๆ ด้วยจำนวนน้อยที่สุด

กราฟแต่ละรูปนี้เราระบายสีจุดของมันด้วยสีเพียงสองสี ก็เพียงพอที่จะทำให้จุดที่อยู่ติดกันมีสีต่างกัน กราฟบางรูปเราต้องใช้สีต่าง ๆ มากมายหลายสี จึงจะพอที่จะระบายให้จุดถัดกันมีสีต่างกัน จะเห็นได้โดยง่ายว่า กราฟต่อไปนี้ต้องใช้สามสี สี่สี ห้าสี ตามลำดับ จึงจะสามสารถทำให้จุดติดกันมีสีต่างกัน

เราเรียกจำนวนสีอย่างน้อยที่สุด ที่พอเพียงที่จะระบายจุดของกราฟให้จุดติดกันมีสีต่างกันว่า จำนวนสีของกราฟ

เหตุหนึ่งที่ทำให้ปัญหาเกี่ยวกับการระบายสีจุดของกราฟ ได้รับความสนใจศึกษาค้นคว้าเป็นอันมาก ได้แก่ ความเกี่ยวข้องกันระหว่างปัญหาเช่นนี้กับปัญหาเกี่ยวกับการระบายสีแผนที่ โดยไม่ให้เนื้อที่ ซึ่งมีเส้นเขตแดนร่วมกันมีสีเดียวกัน เราอาจพิจารณาให้เห็นความเกี่ยวข้องอันนี้ได้ไม่ยากนัก

ในแผนที่นี้ ถ้าเราแทนจังหวัดต่าง ๆ ด้วยจุด แล้วลากเส้นโยงจุด ซึ่งแทนจังหวัดที่มีเส้นเขตแดนร่วมกัน เราจะได้กราฟของแผนที่นี้ ดังรูป จะเห็นได้ว่า ปัญหาการระบายสีแผนที่กับปัญหาการระบายสีจุดของกราฟดังกล่าวไว้นั้น แท้จริงก็คือปัญหาเดียวกัน

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

แม้ทฤษฎีว่าด้วยกราฟตั้งต้นมาตั้งแต่สมัยของออยเลอร์ แต่ก็เพิ่งได้รับความสนใจกันจริงจังในยุคนี้นี่เอง วิชานี้จึงยังต้องการนักคิดให้ช่วยกันค้นคว้าหาคำตอบของปัญหาต่าง ๆ อีกมากมาย