| ปัญหาเกี่ยวกับการเดินข้ามสะพานนั้น เมื่อแปลงมาเป็นภาษาของทฤษฎีว่าด้วยกราฟ ก็กลายเป็นปัญหาที่ว่า เราจะเริ่มต้นจากจุดใดจุดหนึ่ง ลากทับรอยเส้นต่างๆ ในกราฟรูปนี้ให้ครบทุกเส้น เส้นละครั้งเดียวแล้วในที่สุด ลากมาบรรจบที่จุดตั้งต้นได้หรือไม่ | |||
| ออยเลอร์มิได้จำกัดการแก้ปัญหาทำนองนี้กับกราฟรูปนี้เพียงรูปเดียว เขาพิสูจน์ทฤษฎีบท ซึ่งอาจนำไปใช้กับกราฟรูปใดๆ ก็ได้ การลองแก้ปัญหาในทำนองที่กล่าวไว้ข้างต้นกับกราฟทางซ้ายมือ คงจะช่วยให้เราเข้าในทฤษฎีบทของออยเลอร์ได้ดีขึ้น | ||
ในกราฟรูป ก. ถ้าเราตั้งต้นจากจุดใดจุดหนึ่ง แล้วลากทับรอยเส้นกราฟไปในทางใดทางหนึ่งเรื่อยๆ ไป ในที่สุดเราจะกลับมาถึงจุดเดิมได้ โดยลากผ่านเส้นต่างๆ ครบทุกเส้น และเส้นละครั้งเดียว สำหรับกราฟรูป ข. นั้นเราก็อาจตั้งต้นจากจุดใดๆ ลากทับรอยเส้นต่างๆ ไปเรื่อย ให้ครบทุกเส้น เส้นละครั้งเดียว แล้วกลับมาบรรจบที่จุดเดิมได้ไม่ยากนัก แต่เราคงพบอุปสรรคในการลากทับรอยเส้นของกราฟรูป ค.
เพื่อความสะดวกในการกล่าวข้อความในตอนต่อๆ ไป เราจะเรียกกราฟใดๆ ที่เราอาจเริ่มต้นจากจุดใดจุดหนึ่ง ลากทับรอยเส้นของมันไปเรื่อยๆ ให้ครบทุกเส้น เส้นละครั้งเดียว แล้วในที่สุดกลับมาบรรจบที่จุดเดิมนี้ว่า กราฟที่ลากได้ ขอให้สังเกตว่า ในกราฟแต่ละรูปที่เราลากได้นั้น จำนวนเส้นที่เราลากเข้าหาจุดใดๆ ต้องเป็นจำนวนคู่เสมอ ดังนั้นกราฟที่ลากได้แต่ละรูปจำต้องมีจำนวนของเส้นที่พบกันที่แต่ละจุดเป็นจำนวนคู่ หากกราฟใดมีจุดสักจุดหนึ่ง หรือหลายๆ จุด ซึ่งเป็นที่พบกันของเส้นต่างๆ ที่มีจำนวนเส้นเป็นเลขคี่ กราฟนั้นย่อมไม่เป็นกราฟที่ลากได้ เนื่องจากในกราฟแสดงสะพานตามปัญหาข้างต้น จุดต่างๆ เป็นที่พบกันของเส้น ๓ เส้นบ้าง ๕ เส้นบ้าง กราฟนี้จึงไม่ใช่กราฟที่ลากได้ ดังนั้นคำตอบของปัญหาการเดินข้ามสะพานข้างต้นก็คือ เราจะเดินข้ามสะพานตามเงื่อนไขดังกล่าวไม่ได้ นอกจากในการศึกษาปัญหาเกี่ยวกับการลากเส้นตามรอยเส้นกราฟดังได้กล่าวมาแล้ว จำนวนของเส้นที่พบกันที่แต่ละจุดของกราฟ ยังมีบทบาทในการศึกษาปัญหาอย่างอื่นอีกด้วย ในภาษาของทฤษฎีว่าด้วยกราฟ เราเรียกจำนวนของเส้นที่พบกันที่จุดใดๆ ของกราฟว่า ดีกรีของจุดนั้น เช่น แต่ละจุดในกราฟรูป ก. เป็นจุดที่มีดีกรี ๒ ส่วนกราฟรูป ข. ประกอบด้วยจุดที่มีดีกรี ๒ สี่จุด กับจุดที่มีดีกรี ๔ หนึ่งจุด ดังนั้น เราอาจกล่าวข้อสรุปข้างต้นเสียใหม่ด้วยภาษาของวิชาทฤษฎีด้วยกราฟได้ว่า ในกราฟที่ลากได้ จุดทุกจุดต้องมีดีกรีเป็นเลขคู่ ข้อน่าคิดต่อไปก็คือ บทกลับของข้อสรุปข้างบนนี้เป็นจริงหรือไม่ คือ ถ้ากราฟรูปหนึ่งมีแต่จุดที่มีดีกรีเป็นเลขคู่ กราฟรูปนั้นจำต้องเป็นกราฟที่ลากได้เสมอไปหรือไม่ เราจะพบว่า บทกลับนี้ไม่จำเป็นต้องเป็นจริงเสมอไป เช่น ถ้าสะพานเชื่อมโยงเกาะกับฝั่งเป็นดังในรูปข้างล่างนี้
| |||
เราจะพบว่ากราฟแสดงการเชื่อมโยงแผ่นดินทั้งสี่ด้วยสะพาน เป็นกราฟซึ่งแต่ละ จุดมีดีกรีที่ 2 แต่กราฟนี้ มิได้เป็นรูปที่ติดต่อเป็นชิ้นเดียวกัน จึงไม่เป็นกราฟที่ลาก ได้ ดังนั้นคุณสมบัติอีกอย่างหนึ่ง ซึ่งกราฟที่ลากได้จะต้องมีเสมอไปก็คือ การ มีลักษณะติดต่อเป็นชิ้นเดียว | |||
ทฤษฎีบทว่าด้วยกราฟที่ลากได้ ซึ่งออยเลอร์พิสูจน์ไว้กล่าวว่า กราฟรูปหนึ่งรูปใดจะเป็นกราฟที่ลากได้ ก็ต่อเมื่อกราฟนั้นติดต่อ เป็นชิ้นเดียว และจุดทุกจุดมีดีกรีคู่เท่านั้น ปัจจุบันนี้เราเรียกกราฟเช่นนี้ว่า กราฟแบบออยเลอเรียน (Eulerien) |
| ปัญหาเกี่ยวกับการลากทับเส้นกราฟอีกประเภทหนึ่ง ซึ่งคล้ายกับปัญหาข้างต้น ปัญหาประเภทนี้มีว่า เราจะลากทับรอยเส้นกราฟไปเรื่อยๆ โดยให้ผ่านจุดต่างๆ ของกราฟนั้นทุกจุด จุดละครั้งเดียว แล้วในที่สุดกลับมาบรรจบที่จุดเดิมได้หรือไม่ ถ้าเราลองพิจารณากราฟในรูป ก. ข. ค. ในตัวอย่างข้างต้น เราจะพบว่ากราฟ รูป ก. กับ ค. นั้นเราทำได้ ส่วนกราฟรูป ข. นั้น เราจะลากไม่ได้ วิธีลากทับรอยกราฟ รูป ค. ให้ผ่านทุกจุด จุดละครั้งเดียว และกลับมาถึงจุดเดิมนั้นเราอาจทำได้ตามวิธีใดวิธีหนึ่ง ดังแสดงในรูปต่อไปนี้ | |
| |
| กราฟซึ่งเราสามารถลากทับรอยเส้นให้ผ่านทุกจุด จุดละครั้งเดียวและกลับมาบรรจบที่จุดเดิมได้ เราเรียกว่า กราฟแบบแฮมิลโทเนียน (Hamiltonian) ตามชื่อของเซอร์ วิลเลี่ยม โรแวน แฮมิลทัน นักคณิตศาสตร์ชาวอังกฤษ ซึ่งเป็นผู้หยิบปัญหาเช่นนี้ขึ้นพิจารณา | |
| สาเหตุที่ทำให้เราลากให้ผ่านทุกจุดของกราฟ ข. จุดละครั้งเดียวไม่ได้ก็คือจุดๆ หนึ่ง ในกราฟรูปนี้ มีคุณสมบัติพิเศษบางประการ |
| ในรูปกราฟ ข. นี้ หากเราลบจุดหมายเลข ๓ และลบทุกเส้นที่ต่อกับจุดนี้ออกเสีย เราจะได้กราฟที่เป็นสองส่วนแยกจากกัน เราเรียกจุด เช่นนี้ว่า จุดตัด จุดตัดจึงเป็นทางผ่านเพียงทางเดียว ที่เชื่อมต่อกราฟสองชิ้น ถ้าเริ่มต้นจากจากจุดใดจุดหนึ่ง แล้วลากให้ผ่านทุกๆ จุด ในกราฟ เราย่อมต้องลากผ่านจุดตัดถึงสองครั้งเป็นอย่างหนึ่ง เราจึงสรุปได้ว่า กราฟที่มีจุดตัดย่อม ไม่เป็นกราฟแบบแฮมิลโทเนียน บทกลับของข้อสรุปนี้ไม่เป็นจริง กล่าวคือ กราฟที่ไม่มีจุดตัดเลย แต่ไม่เป็นกราฟแบบแฮมิลโทเนียนก็มี รูปต่อไปนี้เป็นกราฟเช่นนั้น | |
| |
| นักคณิตศาสตร์ยุคปัจจุบัน ได้พยายามค้นหาเงื่อนไข ที่สะดวกต่อการใช้เป็นเกณฑ์พิจารณาว่า กราฟรูปใดรูปหนึ่งเป็นกราฟแบบแฮมิลโทเนียนหรือไม่ แต่ก็ยังไม่มีผู้ใดค้นพบเงื่อนไขที่ดีเท่าเทียมกับเงื่อนไข ที่ใช้ในการพิจารณาว่า กราฟเป็นแบบออยเลอเรียนหรือไม่ เช่น มีผู้พบว่า กราฟใดๆ ที่มีสามจุดขึ้นไป และติดต่อกันเป็นชิ้นเดียว ถ้าผลรวมของดีกรี ของจุดที่ไม่ได้อยู่ติดกันแต่ละคู่ ไม่น้อยกว่าจำนวนจุดทั้งหมดในกราฟนั้น กราฟนั้นย่อมเป็นแบบแฮมิลโทเนียน ส่วนที่ยังไม่ค่อยจะดีนักของทฤษฎีบทนี้ ก็คือ เราไม่สามารถใช้ทฤษฎีบทนี้เพียงบทเดียว ตรวจสอบว่า กราฟเป็นแบบแฮมิลโทนเนียนหรือไม่ ได้ทุกรูป เพราะกราฟแบบแฮมิลโทเนียนบางรูป ที่ไม่เป็นไปตามเงื่อนไข ของทฤษฎีบทนี้ก็มี เช่น รูปทางซ้ายมือ เป็นกราฟแบบแฮมิลโทเนียน ซึ่งจุดคู่ที่ห่างกันมีดีกรีรวมกันได้น้อยกว่าจำนวนของจุดในรูป |
การเขียนกราฟแสดงความสัมพันธ์ระหว่างสิ่งต่างๆ นั้นอาจเป็นได้ว่า คนสองคนเขียนกราฟแสดงความสัมพันธ์อันเดียวกัน แต่ได้กราฟที่ต่างกัน เช่น ถ้าคนสี่คน ก ข ค ง ต่างก็รู้จักกันทั้งหมด และมีอยู่คนเดียวในสี่คน คือ ก ที่รู้จักกับ จ อีกคนหนึ่ง เราอาจแสดงการรู้จักกันของคนเหล่านี้ได้โดยใช้จุดแทนคนแล้วลากเส้นโยงจุด ซึ่งแทนคนที่รู้จักกันเป็นคู่ๆ ไป รูปต่อไปนี้ต่างเป็นกราฟแสดงการรู้จักกันของคนเหล่านี้
| |
ในกราฟรูปที่สองนี้ ขอให้คิดเสียว่า เป็นกราฟซึ่งสร้างขึ้นในสามมิติ เส้นซึ่งโยง ก กับ ค และ ข กับ ง นั้นมิได้ตัดกัน แต่ข้ามและลอดซึ่งกันและกันดังเช่นสะพานกับแม่น้ำ อย่างไรก็ตาม ในการศึกษาเกี่ยวกับกราฟ เราศึกษาโดยการเขียนรูปลงบนแผ่นกระดาษ (หรือแผ่นอย่างอื่น) ดังนั้นบางครั้งเราอาจจำยอมเขียนให้เส้นกราฟตัดกัน แต่ไม่นับว่า จุดตัดกันของเส้นกราฟเป็นจุดของกราฟของเรา
| |
| กราฟทั้งสองนี้มีรูปต่างกัน ทั้งๆ ที่แต่ละรูปแสดงถึงสิ่งเดียวกัน อาจกล่าวได้ว่า กราฟสองรูปนี้ต่างกันแต่เพียงรูปเท่านั้น โดยสาระอันแท้จริงแล้ว กราฟทั้งสองนี้เหมือนกัน ในกรณีเช่นนี้เราจะกล่าวว่า กราฟทั้งสองเป็นเสมือนกราฟเดียวกัน ต่อไปนี้เป็นตัวอย่างของกราฟ ซึ่งเป็นเสมือนกราฟเดียวกัน | |
| |
กราฟ ข
| การสร้างกราฟในสามมิติ โดยไม่ให้เส้นกราฟตัดกันนั้นเราทำได้เสมอ แต่ ถ้าจะจำกัดการเขียนให้เส้นกราฟทุกเส้นอยู่บนพื้นราบ เราอาจทำได้สำหรับบางรูป และอาจทำไม่ได้สำหรับบางรูปก็ได้ กราฟแสดงการรู้จักของคนห้าคนในตัวอย่าง ข้างต้น เป็นตัวอย่างของกราฟ ซึ่งเราอาจเขียนลงบนพื้นราบ โดยมิให้เส้นกราฟตัด กันเองเลยได้ โดยทั่วๆ ไปถ้ากราฟใดเป็นเสมือนกราฟเดียวกันกับกราฟรูปใดรูป หนึ่งบนพื้นราบซึ่งไม่มีเส้นคู่ใดตัดกันเลย เราจะกล่าวว่ากราฟนั้นเป็นกราฟที่เขียน ได้บนพื้นราบ ดังนั้นกราฟแสดงการรู้จักกันของคนทั้งห้าในตัวอย่างข้างต้นจึงเป็น กราฟที่เขียนได้บนพื้นราบ แต่ถ้าเราสมมุติเสียใหม่ว่าคนทั้งห้าต่างก็รู้จักกันทุก คู่ กราฟแสดงการรู้จักย่อมเป็นดังนี้ | |
ถ้าเราเขียนรูปของกราฟนี้เสียใหม่ โดยพยายามไม่ให้เส้นกราฟตัดกันเองอย่างดีที่สุด เราคงได้รูปทำนองต่อไปนี้
| |
แต่จะมีเส้นกราฟคู่หนึ่งตัดกันเอง ซึ่งเป็นความจริงที่อาจพิสูจน์ได้สำหรับกราฟรูปนี้ ส่วนกราฟบางรูป เราอาจต้องยอมให้เส้นกราฟตัดกันเองมากกว่าคู่เดียวก็เป็นได้ เราเรียกจำนวนน้อยสุดที่เราจำต้องยอมให้เส้นกราฟตัดกันเอง เมื่อเราเขียนบนพื้นราบว่า จำนวนทางข้ามของกราฟนั้น กราฟแสดงการรู้จักกันของคนห้าคนที่ต่างก็รู้จักกัน จึงเป็นกราฟที่มีจำนวนทางข้ามเป็น ๑ ของกราฟใดๆ ที่เขียนได้บนพื้นราบ ก็คือกราฟที่มีจำนวนทางข้ามเป็น ๐
| |
| กราฟแต่ละรูปนี้เราระบายสีจุดของมันด้วยสีเพียงสองสี ก็เพียงพอที่จะทำให้จุดที่อยู่ติดกันมีสีต่างกัน กราฟบางรูปเราต้องใช้สีต่างๆ มากมายหลายสี จึงจะพอที่จะระบายให้จุดถัดกันมีสีต่างกัน จะเห็นได้โดยง่ายว่า กราฟต่อไปนี้ต้องใช้สามสี สี่สี ห้าสี ตามลำดับ จึงจะสามสารถทำให้จุดติดกันมีสีต่างกัน | |
| |
เราเรียกจำนวนสีอย่างน้อยที่สุด ที่พอเพียงที่จะระบายจุดของกราฟให้จุดติดกันมีสีต่างกันว่า จำนวนสีของกราฟ
หตุหนึ่งที่ทำให้ปัญหาเกี่ยวกับการระบายสีจุดของกราฟ ได้รับความสนใจศึกษาค้นคว้าเป็นอันมาก ได้แก่ ความเกี่ยวข้องกันระหว่างปัญหาเช่นนี้กับปัญหาเกี่ยวกับการระบายสีแผนที่ โดยไม่ให้เนื้อที่ ซึ่งมีเส้นเขตแดนร่วมกันมีสีเดียวกัน เราอาจพิจารณาให้เห็นความเกี่ยวข้องอันนี้ได้ไม่ยากนัก ในแผนที่นี้ ถ้าเราแทนจังหวัดต่างๆ ด้วยจุด แล้วลากเส้นโยงจุด ซึ่งแทนจังหวัดที่มีเส้นเขตแดนร่วมกัน เราจะได้กราฟของแผนที่นี้ ดังรูป จะเห็นได้ว่า ปัญหาการระบายสีแผนที่ กับปัญหาการระบายสีจุดของกราฟดังกล่าวไว้นั้น แท้จริงก็คือปัญหาเดียวกัน
เกี่ยวกับการระบายสีแผนที่นั้น หลายต่อหลายคนเชื่อกันว่า สีเพียงสี่สี ย่อมเพียงพอที่จะระบายแผนที่ใดๆ ให้เนื้อที่ที่มีเส้นเขตแดนร่วมกันมีสีต่างกันได้เสมอ ไม่ว่าเนื้อที่ต่างๆ ในแผนที่นั้นจะเรียงรายกันอยู่อย่างไร นักคณิตศาสตร์ได้พยายามค้นคว้าหาคำตอบว่า เรื่องที่หลายคนเชื่อกันนี้จริงหรือไม่ การขบคิดปัญหานี้ นักคณิตศาสตร์ได้ทำกันมาเป็นเวลานานกว่าร้อยปี จึงมีผู้พิสูจน์ได้ว่า ความเชื่อดังกล่าวถูกต้อง แม้ทฤษฎีว่าด้วยกราฟตั้งต้นมาตั้งแต่สมัยของออยเลอร์ แต่ก็เพิ่งได้รับความสนใจกันจริงจังในยุคนี้นี่เอง วิชานี้จึงยังต้องการนักคิดให้ช่วยกันค้นคว้าหาคำตอบของปัญหาต่างๆ อีกมากมาย | |
