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

ทฤษฎีกราฟเป็นสาขาหนึ่งของคณิตศาสตร์ที่ศึกษากราฟ ซึ่ง เป็นโครงสร้างทางคณิตศาสตร์สำหรับการจำลองความสัมพันธ์แบบคู่ระหว่างวัตถุ เป็นส่วนหนึ่งของคณิตศาสตร์เชิงดิส ครีต มักถูกพิจารณาว่าเป็นส่วนหนึ่งของคณิตศาสตร์เชิงการจัดเรียง แม้ว่าจะเป็นสาขาที่เป็นอิสระเนื่องจากการเติบโตอย่างมากและแตกต่างจากสาขาอื่น ๆ โดยมีปัญหาเฉพาะของตนเอง^{[ 1 ]}คำว่า "กราฟ" ถูกนำมาใช้โดยเจมส์ โจเซฟ ซิลเวสเตอร์ในบทความที่ตีพิมพ์ในปี 1878 ในNatureโดยเขาเปรียบเทียบระหว่าง "ตัวแปรควอนตัม" และ "ตัวแปรร่วม" ของพีชคณิตและแผนภาพโมเลกุล^{[ 2 ]}

นิยามของกราฟอาจแตกต่างกันไป แต่เราสามารถเข้าใจได้ว่ากราฟเป็นโครงสร้างที่ประกอบด้วยจุดยอด (เรียกอีกอย่างว่าโหนดหรือจุด) และขอบ (เรียกอีกอย่างว่าส่วนโค้ง ลิงก์ หรือเส้น) จุดยอดสองจุดของขอบเรียกว่าจุดปลาย^{[ 3 ]}บางครั้งกราฟจะถูกเรียกว่ากราฟแบบไม่มีทิศทาง เพื่อแยกความแตกต่างจากกราฟแบบมีทิศทางกราฟแบบมีทิศทางคือกราฟที่แต่ละขอบมีทิศทางที่กำหนดไว้ ซึ่งเรียกว่าการวางแนว โดยกำหนดด้วยลูกศร^{[ 4 ]}กราฟแบบผสมสามารถมีขอบที่อาจมีทิศทาง และบางขอบอาจไม่มีทิศทาง^{[ 5 ]}กราฟยังสามารถเรียกว่ากราฟแบบง่าย เพื่อแยกความแตกต่างจากมัลติกราฟมัลติกราฟอนุญาตให้ขอบหลายเส้นมีจุดปลายคู่เดียวกัน และยังอนุญาตให้ขอบเชื่อมต่อจุดยอดกับตัวเอง ซึ่งเรียกว่าวงวน [ ^{6 ]}กราฟสามารถกำหนดหมายเลขให้กับขอบได้ ซึ่งเรียกว่าน้ำหนัก กราฟดังกล่าวเรียกว่ากราฟแบบมี ^{น้ำหนัก}

ในปี ค.ศ. 1736 เลออนฮาร์ด ออยเลอร์ ได้ตีพิมพ์บทความชื่อSolutio Problematis ad Geometriam Situs Pertinentisเกี่ยวกับสะพานเจ็ดแห่งของเมืองเคอนิกส์เบิร์กซึ่งถือเป็นบทความแรกในประวัติศาสตร์ของทฤษฎีกราฟ^{[ 7 ]}บทความของออยเลอร์และ บทความ Remarques sur les Problèmes de Situationในปี ค.ศ. 1771 ของอเล็กซานเดอร์-เธโอฟิล แวนเดอร์มอน ด์ เกี่ยวกับ การเดินทางของอัศวินได้ดำเนินการต่อด้วยการวิเคราะห์ situsซึ่งริเริ่มโดยก็อตฟรีด วิลเฮล์ม ไลบ์นิซ^{[ 8 ]}ลักษณะเฉพาะของออยเลอร์ที่เชื่อมโยงจำนวนขอบ จุดยอด และหน้าของรูปทรงหลายเหลี่ยมนูน ได้รับการศึกษาและสรุปโดยออกัสติน-หลุยส์ โคชีและไซมอน อองตวน ฌอง ลูอิลิเยร์^{[ 9 ]}และเป็นจุดเริ่มต้นของสาขาคณิตศาสตร์ที่รู้จักกันในชื่อโทโพโลยี^{[ 10 ]}

กว่าหนึ่งศตวรรษหลังจากบทความของออยเลอร์เกี่ยวกับสะพานแห่งเคอนิกส์เบิร์กและในขณะที่โยฮันน์ เบเนดิกต์ ลิสติงกำลังนำเสนอแนวคิดของโทโพโลยีอาร์เธอร์ เคย์ลีย์ได้รับแรงบันดาลใจจากรูปแบบการวิเคราะห์เฉพาะที่เกิดขึ้นจากแคลคูลัสเชิงอนุพันธ์เพื่อศึกษากราฟประเภทหนึ่งโดยเฉพาะนั่น คือ ต้นไม้^{[ 11 ]}การศึกษานี้มีนัยสำคัญมากมายต่อเคมี เชิงทฤษฎี เทคนิคที่เขาใช้ส่วนใหญ่เกี่ยวข้องกับการนับกราฟที่มีคุณสมบัติเฉพาะ ทฤษฎีกราฟเชิงนับจึงเกิดขึ้นจากผลลัพธ์ของเคย์ลีย์และผลลัพธ์พื้นฐานที่ตีพิมพ์โดยโปลยาระหว่างปี 1935 ถึง 1937 ซึ่งได้รับการสรุปโดยนิโคลาส โกเวิร์ต เดอ บรูอินในปี 1959 เคย์ลีย์เชื่อมโยงผลลัพธ์ของเขาเกี่ยวกับต้นไม้กับการศึกษาองค์ประกอบทางเคมีในยุคนั้น^{[ 11 ]}การผสมผสานแนวคิดจากคณิตศาสตร์กับแนวคิดจากเคมีได้เริ่มต้นสิ่งที่กลายเป็นส่วนหนึ่งของศัพท์เฉพาะมาตรฐานของทฤษฎีกราฟ

การพัฒนาอย่างอิสระของวิชาโทโพโลยีตั้งแต่ปี 1860 ถึง 1930 ได้ก่อให้เกิดทฤษฎีกราฟขึ้นมาใหม่ผ่านผลงานของCamille Jordan , Kazimierz KuratowskiและHassler Whitneyปัจจัยสำคัญอีกประการหนึ่งในการพัฒนาร่วมกันของทฤษฎีกราฟและโทโพโลยีมาจากการใช้เทคนิคของพีชคณิตสมัยใหม่ ตัวอย่างแรกของการใช้งานดังกล่าวมาจากผลงานของนักฟิสิกส์Gustav Kirchhoffซึ่งตีพิมพ์กฎวงจรของ Kirchhoff ในปี 1845 สำหรับการคำนวณแรงดันและกระแสในวงจรไฟฟ้า

ตำราเล่มแรกเกี่ยวกับทฤษฎีกราฟเขียนโดยDénes Kőnigและตีพิมพ์ในปี 1936 ^{[ 12 ]}หนังสืออีกเล่มหนึ่งโดยFrank Hararyซึ่งตีพิมพ์ในปี 1969 ได้รับการยกย่องว่าเป็นตำราที่สมบูรณ์ที่สุดในเรื่องนี้ทั่วโลก^{[ 13 ]}และทำให้เหล่านักคณิตศาสตร์ นักเคมี วิศวกรไฟฟ้า และนักสังคมศาสตร์สามารถพูดคุยกันได้ Harary บริจาคค่าลิขสิทธิ์ทั้งหมดเพื่อเป็นทุนสนับสนุนรางวัลPólya ^{[ 14 ]}

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

ปัญหาสี่สียังคงไม่ได้รับการแก้ไขมานานกว่าศตวรรษ ในปี 1969 ไฮน์ริช ฮีสช์ได้ตีพิมพ์วิธีการแก้ปัญหาโดยใช้คอมพิวเตอร์^{[ 15 ]}การพิสูจน์โดยใช้คอมพิวเตอร์ช่วยที่สร้างขึ้นในปี 1976 โดยเคนเนธ แอปเปลและโวล์ฟกัง ฮาเคนได้ใช้แนวคิดพื้นฐานของ "การปล่อยประจุ" ที่พัฒนาโดยฮีสช์^{[ 16 ] [ 17 ]}การพิสูจน์เกี่ยวข้องกับการตรวจสอบคุณสมบัติของการกำหนดค่า 1,936 แบบโดยใช้คอมพิวเตอร์ และไม่ได้รับการยอมรับอย่างเต็มที่ในขณะนั้นเนื่องจากความซับซ้อน การพิสูจน์ที่ง่ายกว่าโดยพิจารณาเพียง 633 การกำหนดค่า ได้รับการนำเสนอในอีกยี่สิบปีต่อมาโดยโรเบิร์ตสัน ซีมัวร์แซนเดอร์สและโทมัส^{[ 18 ]}

การนำวิธีการทางความน่าจะเป็นมาใช้ในทฤษฎีกราฟ โดยเฉพาะอย่างยิ่งในการศึกษาของErdősและRényiเกี่ยวกับความน่าจะเป็นเชิงอะซิมโทติกของการเชื่อมต่อกราฟ ทำให้เกิดสาขาใหม่ขึ้นมาอีกสาขาหนึ่ง ซึ่งรู้จักกันในชื่อทฤษฎีกราฟสุ่มซึ่งเป็นแหล่งที่มาของผลลัพธ์ทางทฤษฎีกราฟ ที่อุดมสมบูรณ์ ^{[ 19 ]}

ทฤษฎีกราฟเชิงทอพอโลยีเกี่ยวข้องกับการศึกษากราฟที่สัมพันธ์กับทอพอโลยี หัวข้อต่างๆ พร้อมภาพประกอบจากบนลงล่างที่ให้มา มีดังนี้

• การฝังกราฟลงบนพื้นผิว โดยมีตัวอย่างกราฟ Heawoodในทอรัส
• การฝัง กราฟรูปเพชร1 หน้า ;
• จำนวนจุดตัดโดยมีตัวอย่างของกราฟสองส่วนสมบูรณ์ที่มีสี่และเจ็ดจุดยอดซึ่งมีจุดตัด 18 จุด (จุดสีแดง); และ${\displaystyle K_{4,7}}$
• การระบายสีแผนที่ โดยใช้ทฤษฎีสี่สีในการระบายสีแต่ละรัฐในสหรัฐอเมริกา ให้แตกต่างกัน โดยไม่รวมทะเลสาบและมหาสมุทร

ทฤษฎีกราฟเชิงโทโพโลยีเกี่ยวข้องกับการศึกษากราฟในฐานะพื้นที่เชิงโทโพโลยี กราฟในโทโพโลยีคือเซตของซิมเพล็กซ์ที่เรียกว่าคอมเพล็กซ์มิติเดียวเชิง ซิมเพล็ก ซ์^{[ 20 ]}สาขาย่อยนี้ศึกษาการฝัง ( หรือการฝัง) ของกราฟในพื้นผิวและการฝังแบบไม่มีลิงก์ไมเนอร์กราฟจำนวนจุดตัดการระบายสีแผนที่ และกราฟแรงดันไฟฟ้า^{[ 21 ]}

การฝังกราฟลงบนพื้นผิวคือการแสดงกราฟโดยที่จุดต่างๆ เชื่อมโยงกับจุดยอด และส่วนโค้งแบบง่ายเชื่อมโยงกับขอบบนพื้นผิว จุดปลายเชื่อมโยงกับขอบ และจุดต่างๆ เชื่อมโยงกับจุดยอดปลาย ส่วนโค้งใดๆ ก็ตามจะไม่รวมจุดที่เชื่อมโยงกับจุดยอดอื่นๆ และส่วนโค้งสองส่วนจะไม่ตัดกันที่จุดที่อยู่ภายในส่วนโค้งใดส่วนโค้งหนึ่ง การฝังกราฟสามารถขยายไปสู่การฝังแบบไม่มีการเชื่อมโยงได้ โดยที่ไม่มีวงจรสองวงใดของกราฟเชื่อมโยงกันในปริภูมิยูคลิดสามมิติ^{[ 22 ]}และหนังสือซึ่งเป็นชุดของระนาบครึ่งที่มีเส้นเดียวกันเป็นขอบเขต^{[ 23 ]}

กล่าวกันว่ากราฟนั้นเป็นกราฟย่อย หากสามารถสร้างจากกราฟอื่นได้โดยการลบจุดยอดและขอบ และโดย การ หดตัวของขอบ^{[ 22 ]}ผลลัพธ์แรกสุดของทฤษฎีกราฟย่อยมาจากทฤษฎีบทของ Wagnerซึ่งระบุว่ากราฟจำกัดเป็นกราฟระนาบก็ต่อเมื่อกราฟย่อยของมันไม่มีทั้งกราฟสมบูรณ์บนจุดยอดห้าจุด หรือกราฟยูทิลิตี้ [ ^{24 ]}ผลลัพธ์ที่เกี่ยวข้องคือทฤษฎีบท Robertson–Seymourซึ่งบ่งชี้ถึงการมีอยู่ของ กราฟ ย่อยต้องห้ามสำหรับทุกคุณสมบัติของกราฟที่คงไว้โดยการลบและการหดตัวของ^{ขอบ[ 25 ]}${\displaystyle K_{5}}$

จำนวนจุดตัดจะบอกจำนวนขอบที่ตัดกันขั้นต่ำของกราฟ การศึกษานี้มีต้นกำเนิดมาจากนักคณิตศาสตร์ชาวฮังการีชื่อPál Turánซึ่งได้ขอแผนโรงงานที่ลดจำนวนจุดตัดระหว่างรางที่เชื่อมต่อเตาเผาอิฐกับสถานที่จัดเก็บให้น้อยที่สุดปัญหานี้สามารถกำหนดเป็นทางการได้โดยการขอจำนวนจุดตัดของกราฟสองส่วนที่สมบูรณ์^{[ 26 ]}

การระบายสีกราฟเป็นการกำหนดป้ายกำกับองค์ประกอบของกราฟอย่างเป็นระบบ ซึ่งโดยทั่วไปเรียกว่าสีในการระบายสีนั้น ไม่มีองค์ประกอบที่อยู่ติดกันสององค์ประกอบใดที่มีสีเดียวกัน ต้องใช้จำนวนสีขั้นต่ำ ซึ่งเรียกว่าจำนวนโครมาติกทฤษฎีบทสี่สีระบุว่าไม่จำเป็นต้องใช้สีมากกว่าสี่สีในการระบายสีบริเวณของแผนที่ใดๆ โดยที่ไม่มีบริเวณที่อยู่ติดกันสองบริเวณใดที่มีสีเดียวกัน กล่าวคือ ไม่มีสองบริเวณใดที่มีขอบเขตร่วมกัน^{[ 27 ]}ทฤษฎีบทนี้แข็งแกร่งกว่าทฤษฎีบทห้าสีในทำนองเดียวกันปัญหาโลก-ดวงจันทร์เป็นที่รู้จักกันในฐานะปัญหาเปิดในปัจจุบันเกี่ยวกับการขยายปัญหาการระบายสีแผนที่ระนาบ ซึ่งแก้ไขโดยทฤษฎีบทสี่สี

กราฟแรงดันไฟฟ้าเป็นกราฟแบบมีทิศทางซึ่งขอบจะถูกระบุโดยองค์ประกอบของกลุ่ม แบบผกผันได้ กราฟนี้ระบุถึงกราฟที่ได้มาอย่างกระชับ[ 28 ^{]นอกจากนี้}ยังเป็นวิธีทั่วไปในการสร้างกราฟครอบคลุม อีกด้วย ^{[ 29 ]}

ทฤษฎีกราฟเชิงพีชคณิตคือการศึกษาทฤษฎีกราฟที่เกี่ยวข้องกับสาขาหลักของพีชคณิตสาขาหลักของพีชคณิตที่ใช้ ได้แก่พีชคณิตเชิงเส้นและทฤษฎี กลุ่ม

การศึกษาทฤษฎีกราฟโดยใช้พีชคณิตเชิงเส้นเรียกว่าทฤษฎีกราฟเชิงสเปกตรัมการศึกษานี้มุ่งเน้นไปที่เมทริกซ์ประชิดซึ่งเป็นเมทริกซ์ที่แสดงถึงกราฟ และสเปกตรัมของเมทริกซ์ประชิดซึ่งมุ่งเน้นไปที่พหุนามลักษณะเฉพาะค่าลักษณะเฉพาะ และเวกเตอร์ลักษณะเฉพาะ ของเมทริกซ์ประชิดที่กำหนด นอกจากนี้ยังมุ่งเน้นไปที่ เมทริกซ์ลาปลาเซียนของกราฟ ซึ่งเกี่ยวข้องกับเมทริกซ์ดีกรี ( เมทริกซ์แนวทแยงที่แสดงถึงดีกรีของจุดยอด) และเมทริกซ์ประชิด^{[ 30 ]}

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

ทฤษฎีกราฟเชิงพีชคณิตยังศึกษาตัวแปร เชิงพีชคณิต พหุนามสีพหุนาม Tutteของกราฟ และตัวแปรปม [ ^{32 ] ตัวแปร}กราฟคือคุณสมบัติของกราฟที่ขึ้นอยู่กับโครงสร้างนามธรรมเท่านั้น แทนที่จะเป็นการติดป้ายหรือการวาดกราฟ พหุนามสีคือพหุนามที่นับจำนวนการระบายสีกราฟเป็นฟังก์ชันของจำนวนสี^{[ 34 ]}พหุนาม Tutte คือพหุนามสองตัวแปรบนการเชื่อมต่อของกราฟ^{[ 35 ]}

ทฤษฎีกราฟเชิงเรขาคณิตศึกษาเกี่ยวกับกราฟที่วาดด้วยเส้นตรงหรือเส้นโค้งต่อเนื่องที่มีคุณสมบัติทางเรขาคณิตในเชิงการจัดเรียง ในภาพประกอบเหล่านี้ ทฤษฎีกราฟเชิงเรขาคณิตศึกษา:

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

ทฤษฎีกราฟเชิงเรขาคณิตมุ่งเน้นไปที่คุณสมบัติเชิงการจัดเรียงและเชิงเรขาคณิตของกราฟที่วาดในระนาบที่มีขอบเส้นตรงหรือเส้นโค้งต่อเนื่องในปริภูมิยุคลิด [ ^{36 ] ใน}ฐานะส่วนหนึ่งของเรขาคณิตแบบไม่ต่อเนื่องและเรขาคณิตเชิงคำนวณทฤษฎีกราฟเชิงเรขาคณิตศึกษากราฟระนาบ [ ^{37 ] ความ}สัมพันธ์กับโพลีโทปนูนมิติสูง [ ^{38 ]}จุดตัด ของเซต ^รูปทรงเรขาคณิต^{[ 39 ]}และสาขาย่อยอื่นๆ ของเรขาคณิตเชิงเหตุการณ์และเรขาคณิตเชิงฉาย^{[ 40 ]}

กราฟระนาบที่จุดยอดฝังตัวเป็นจุด และขอบเป็น ส่วนของเส้นตรงที่ไม่ตัดกันในระนาบยุคลิดเรียกว่ากราฟเส้นตรงระนาบกราฟระนาบใดๆ ก็สามารถแสดงเป็นกราฟเส้นตรงระนาบได้โดยทฤษฎีบทของ Fáryกราฟเส้นตรงระนาบเป็นกรณีพิเศษของกราฟยุคลิด กราฟยุคลิดอนุญาตให้ขอบมีความยาวเท่ากับระยะทางยุคลิดระหว่างจุดปลาย แนวคิดของมันคือต้นไม้แผ่คลุมขั้นต่ำยุคลิดเกี่ยวกับการลดความยาวรวมของส่วนของเส้นตรงสำหรับจุดจำกัดในปริภูมิยุคลิดใด ๆ ปัญหา Hadwiger–Nelsonเกี่ยวกับการถามถึงจำนวนระนาบการระบายสีขั้นต่ำที่ไม่มีจุดสองจุดที่อยู่ห่างกันหนึ่งหน่วยมีสีเดียวกัน และปัญหาเส้นทางที่สั้นที่สุดเกี่ยวกับการหาเส้นทางระหว่างจุดยอดสองจุดในกราฟที่ลดผลรวมของค่าที่กำหนดให้กับขอบให้น้อยที่สุด^{[ 37 ]}

กราฟการมองเห็นคือกราฟที่มีจุดยอดและขอบเป็นตำแหน่งจุดและการเชื่อมต่อที่มองเห็นได้ตามลำดับ ในรูปหลายเหลี่ยมแบบง่ายซึ่งขอบของมันไม่ตัดกันเองและไม่มีรู จุดยอดของกราฟการมองเห็นจะเชื่อมต่อกันด้วยขอบที่แสดงถึงด้านและเส้นทแยงมุมของรูปหลายเหลี่ยม จุดยอดถูกกำหนดให้เป็นตำแหน่งจุด^{[ 41 ]}กราฟทรงหลายเหลี่ยม เป็นกราฟแบบไม่มีทิศทางที่สร้างจุดยอดและขอบของ ทรงหลายเหลี่ยมนูนสามมิติเพื่อให้ได้มาซึ่งกราฟดังกล่าว กราฟนั้นต้องเป็นไปตามข้อกำหนดของทฤษฎีบทของสไตน์นิทซ์ซึ่งระบุว่าทรงหลายเหลี่ยมนูนทุกรูปเป็นกราฟระนาบที่เชื่อมต่อกันด้วย 3 จุดยอดกราฟระนาบยังคงเชื่อมต่อกันเมื่อใดก็ตามที่จุดยอดสองจุดใดๆ ถูกลบออก^{[ 42 ]}

กราฟจุดตัดคือกราฟที่แต่ละจุดยอดเชื่อมโยงกับเซต และจุดยอดจะเชื่อมต่อกันด้วยขอบเมื่อใดก็ตามที่เซตที่สอดคล้องกันมีจุดตัด ที่ไม่ว่าง เปล่า^{[ 39 ]}แต่ละจุดยอดแสดงเป็นเซต และจุดยอดสองจุดทุกคู่จะเชื่อมต่อกัน ดังนั้น กราฟจุดตัดของเซตจำกัดสามารถแสดงได้ด้วยจำนวนองค์ประกอบที่จำเป็นน้อยที่สุด ซึ่งเรียกว่าจำนวนจุดตัดกราฟผลลัพธ์สามารถเป็นกราฟเรขาคณิตได้เมื่อใดก็ตามที่เซตเป็นวัตถุเรขาคณิต ตัวอย่างเช่น กราฟจุดตัดของส่วนของเส้นตรงในมิติเดียวคือกราฟช่วงกราฟจุดตัดของวงกลมหน่วยในระนาบคือกราฟวงกลมหน่วยจุดตัดของการเรียงซ้อนวงกลมคือกราฟเหรียญโดยที่จุดยอดและขอบแทนวงกลมและวงกลมสัมผัสทุกคู่ ตามทฤษฎีบท Koebe–Andreev–Thurston กราฟจุดตัดของวงกลมที่ไม่ตัดกันคือกราฟระนาบ^{[ 43 ]}ทฤษฎีบทของ Scheinermanกล่าวว่ากราฟระนาบทุกกราฟสามารถแสดงเป็นกราฟจุดตัดของส่วนของเส้นตรงในระนาบได้^{[ 44 ]}

กราฟLeviเป็นกราฟสองส่วนที่เชื่อมโยงกับโครงสร้างเหตุการณ์และการกำหนดค่าเชิงฉาย^{[ 40 ]}

การประยุกต์ใช้กับการแสดงภาพข้อมูลนี้ ทำให้เกิดสาขาย่อยอีกสาขาหนึ่งของทฤษฎีกราฟที่เรียกว่าการวาดกราฟซึ่งเป็นการแสดงภาพกราฟ มักจะวาดเป็นแผนภาพโหนด-ลิงก์ โดยจุดยอดของกราฟจะแสดงเป็นวงกลม กล่อง หรือป้ายกำกับข้อความ และขอบจะแสดงเป็นส่วนของเส้นตรง เส้นหลายเหลี่ยม หรือเส้นโค้งในระนาบยูคลิด^{[ 45 ]}คำจำกัดความมากมายสำหรับการวาดกราฟโดยอิงจากการวัดคุณภาพ ได้แก่ จำนวนจุดตัด^{[ 46 ]}พื้นที่การแสดงสมมาตรในการค้นหาปัญหาของออโตมอร์ฟิซึมกลุ่มของกราฟ^{[ 47 ]} การลดการโค้ง งอความละเอียดเชิงมุม^{[ 48 ]}และจำนวนความชัน [ ^{48 ] เครื่องมือ}สำหรับการวาดกราฟ ได้แก่ การจัดเรียงวงกลม^{[ 49 ]}กราฟจุดตัด และการแสดงภาพอื่นๆ ของเมทริกซ์ความประชิด

ทฤษฎีกราฟสุดขั้วเป็นสาขาหนึ่งของคณิตศาสตร์ที่จุดตัดระหว่างคณิตศาสตร์เชิงการจัดเรียงสุดขั้วและทฤษฎีกราฟ สาขานี้ศึกษาจำนวนขอบสูงสุดของกราฟ ซึ่งเรียกว่าจำนวนสุดขั้ว^{[ 50 ]}จุดเริ่มต้นของสาขาย่อยนี้มาจากทฤษฎีบทของ Mantel เกี่ยวกับจำนวนสุดขั้วของกราฟที่ไม่มีสามเหลี่ยมทฤษฎีบทของ Turánได้ขยายทฤษฎีบทของ Mantel สำหรับกราฟแบบไม่มีทิศทางใดๆ ที่ไม่มีกราฟย่อยสมบูรณ์ที่มีขนาดที่กำหนด ทฤษฎีบทของ Turán ได้รับการสรุปโดยทฤษฎีบทของ Erdős–Stoneซึ่งบางครั้งเรียกว่า "ทฤษฎีบทพื้นฐานของทฤษฎีกราฟสุดขั้ว" ^{[ 51 ]}

ทฤษฎีกราฟสุดขั้วยังศึกษาปัญหาของกราฟย่อยต้องห้ามความหนาแน่นของโฮโมมอร์ฟิซึมและทฤษฎีบทความสม่ำเสมอของ Szemerédiปัญหาของกราฟย่อยต้องห้ามชี้ให้เห็นถึงการค้นหาจำนวนสุดขั้วของกราฟที่มีจุดยอดซึ่งไม่มีกราฟย่อยที่เป็นไอโซมอร์ฟิกกับกราฟ^{[ 52 ]}ความหนาแน่นของโฮโมมอร์ฟิซึมเป็นพารามิเตอร์ที่เกี่ยวข้องกับโฮโมมอร์ฟิซึมของกราฟความหนาแน่นอาจหมายถึงความน่าจะเป็นที่แผนที่จากจุดยอดของกราฟหนึ่งไปยังจุดยอดของอีกกราฟหนึ่งที่เลือกแบบสุ่มอย่างสม่ำเสมอเป็นโฮโมมอร์ฟิซึมของกราฟ การเป็นโฮโมมอร์ฟิกหมายความว่ามีแผนที่ระหว่างกราฟสองกราฟที่เคารพโครงสร้างของกราฟเหล่านั้น หรือเทียบเท่ากับฟังก์ชันระหว่างเซตจุดยอดของกราฟสองกราฟที่แมปจุดยอดที่อยู่ติดกันไปยังจุดยอดที่อยู่ติดกัน^{[ 53 ]}ทฤษฎีบทความสม่ำเสมอของ Szemerédi ระบุว่ากราฟสามารถแบ่งออกเป็นจำนวนส่วนที่จำกัดได้ โดยที่ขอบระหว่างส่วนต่างๆ เป็นแบบ -ปกติ ${\displaystyle n}$${\displaystyle \varepsilon }$

ทฤษฎีกราฟสุ่มมุ่งเน้นไปที่กราฟโดยใช้วิธีความน่าจะเป็นสาขาย่อยนี้ก่อตั้งโดยนักคณิตศาสตร์ชาวฮังการีPaul ErdősและAlfréd Rényiซึ่งการสร้างแบบจำลองของพวกเขาสร้างกราฟสุ่มที่เรียกว่าแบบจำลอง Erdős– Rényi ^{[ 19 ]}

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

• ต้นไม้แผ่ขยายแบบสม่ำเสมอ (Uniform spanning tree)คือต้นไม้แผ่ขยายของกราฟที่กำหนด ซึ่งต้นไม้แต่ละต้นที่แตกต่างกันมีโอกาสถูกเลือกเท่าๆ กันการเป็นต้นไม้แผ่ขยายหมายความว่ากราฟย่อยนั้นเป็นต้นไม้ที่รวมจุดยอดทั้งหมดของกราฟ ต้นไม้แผ่ขยายแบบสม่ำเสมอสามารถสร้างได้โดยใช้วิธีเส้นทางสุ่มแบบง่ายที่เรียกว่าการเดินสุ่มแบบลบวงวน (loop-erased random walk ) โดยการเดินสุ่มบนกราฟที่กำหนดและลบวงวนที่สร้างขึ้นโดยการเดินนี้^{[ 54 ]}
• กระบวนการแตกแขนง (Branching process ) คือแบบจำลองของประชากรที่แต่ละบุคคลมีจำนวนบุตรแบบสุ่ม
• ต้นไม้บราวน์ (Brownian tree)คือโครงสร้างต้นไม้แบบแฟร็กทัลที่สร้างขึ้นจากกระบวนการรวมกลุ่มแบบจำกัดการแพร่กระจาย
• ต้นไม้ไบนารีแบบสุ่มคือต้นไม้ไบนารีที่เลือกแบบสุ่มจากการกระจายความน่าจะเป็น บางอย่าง บนต้นไม้ไบนารี^{[ 55 ]}ซึ่งรวมถึงต้นไม้ที่สร้างขึ้นโดยลำดับการแทรกแบบสุ่ม^{[ 56 ]}และต้นไม้ที่กระจายอย่างสม่ำเสมอด้วยจำนวนโหนดที่กำหนด
• Random forestคือตัวจำแนกประเภทด้วยการเรียนรู้ของเครื่องจักร โดยอาศัยการเลือกชุดย่อยของตัวแปรแบบสุ่มสำหรับแต่ละต้นไม้ และใช้ผลลัพธ์จากต้นไม้ที่ปรากฏบ่อยที่สุดเป็นตัวจำแนกประเภทโดยรวม
• ต้นไม้ครอบคลุมขั้นต่ำแบบสุ่มคือต้นไม้ครอบคลุมของกราฟที่สร้างขึ้นโดยการเลือกน้ำหนักขอบแบบสุ่มและใช้ต้นไม้ครอบคลุมขั้นต่ำสำหรับน้ำหนักเหล่านั้น^{[ 57 ]}
• ต้นไม้แบบเรียกซ้ำแบบสุ่มต้นไม้ที่มีป้ายกำกับเพิ่มขึ้นเรื่อยๆ ซึ่งสามารถสร้างได้โดยใช้กฎการเติบโตแบบสุ่มอย่างง่าย
• การสำรวจต้นไม้สุ่มอย่างรวดเร็วซึ่งเป็นรูปแบบแฟร็กทัลที่เติมเต็มพื้นที่และใช้เป็นโครงสร้างข้อมูลสำหรับการค้นหาในพื้นที่มิติสูง
• ต้นไม้ค้นหาแบบไบนารีแบบสุ่ม (Treapหรือ Randomized Binary Search Tree) เป็นโครงสร้างข้อมูลที่ใช้การเลือกแบบสุ่มเพื่อจำลองต้นไม้ไบนารีแบบสุ่มสำหรับลำดับการอัปเดตที่ไม่สุ่ม

กราฟสามารถใช้สร้างแบบจำลองความสัมพันธ์และกระบวนการหลายประเภทในระบบทางกายภาพ ชีวภาพ^{[ 59 ] [ 60 ]}สังคม และระบบสารสนเทศ^{[ 61 ]}ปัญหาในทางปฏิบัติหลายอย่างสามารถแสดงได้ด้วยกราฟ การเน้นการประยุกต์ใช้กับระบบในโลกแห่งความเป็นจริง บางครั้งคำว่าเครือข่ายถูกนิยามให้หมายถึงกราฟที่คุณลักษณะ (เช่น ชื่อ) เชื่อมโยงกับจุดยอดและขอบ และวิชาที่แสดงและเข้าใจระบบในโลกแห่งความเป็นจริงในฐานะเครือข่ายเรียกว่าวิทยาศาสตร์เครือข่าย

ในสาขาวิทยาการคอมพิวเตอร์ โครงสร้างที่เชื่อมโยงแบบ ' มีเหตุผล ' และ 'ไม่มีเหตุผล' คือกราฟที่ใช้ในการแสดงเครือข่ายการสื่อสาร การจัดระเบียบข้อมูล อุปกรณ์คำนวณ การไหลของการคำนวณ ฯลฯ ตัวอย่างเช่น โครงสร้างการเชื่อมโยงของเว็บไซต์สามารถแสดงได้ด้วยกราฟแบบมีทิศทาง ซึ่งจุดยอด (โหนด) แทนหน้าเว็บ และขอบแบบมีทิศทางแทนลิงก์จากหน้าหนึ่งไปยังอีกหน้าหนึ่ง แนวทางที่คล้ายกันนี้สามารถนำไปใช้กับปัญหาในสื่อสังคมออนไลน์^{[ 62 ]}การท่องเที่ยว ชีววิทยา การออกแบบชิปคอมพิวเตอร์ การทำแผนที่ความก้าวหน้าของโรคทางระบบประสาทเสื่อม^{[ 63 ] [ 64 ]}และสาขาอื่นๆ อีกมากมาย ดังนั้น การพัฒนาอัลกอริทึมเพื่อจัดการกับกราฟจึงเป็นที่สนใจอย่างมากในวิทยาการคอมพิวเตอร์การแปลงกราฟมักจะถูกกำหนดรูปแบบและแสดงโดยระบบการเขียนกราฟใหม่ ระบบ การแปลงกราฟที่เน้นการจัดการกราฟในหน่วยความจำตามกฎเกณฑ์นั้นเสริมด้วยฐานข้อมูลกราฟที่มุ่งเน้นการจัดเก็บและสอบถามข้อมูลที่มีโครงสร้างกราฟอย่างปลอดภัยและถาวร สำหรับการ ทำ ธุรกรรม

วิธีการทางทฤษฎีกราฟในรูปแบบต่างๆ ได้พิสูจน์แล้วว่ามีประโยชน์อย่างยิ่งในทางภาษาศาสตร์เนื่องจากภาษาธรรมชาติมักเหมาะสมกับโครงสร้างแบบไม่ต่อเนื่อง ตามธรรมเนียมแล้วไวยากรณ์และอรรถศาสตร์เชิงองค์ประกอบจะใช้โครงสร้างแบบต้นไม้ ซึ่งพลังในการแสดงออกนั้นอยู่ที่หลักการของการประกอบกันโดยจำลองในกราฟแบบลำดับชั้น แนวทางที่ทันสมัยกว่า เช่น ไวยากรณ์ โครงสร้างวลีแบบหัวคำ (head-driven phrase structure grammar)จำลองไวยากรณ์ของภาษาธรรมชาติโดยใช้โครงสร้างคุณลักษณะแบบมีประเภทซึ่งเป็นกราฟแบบมีทิศทางและไม่มีวงจรในด้านอรรถศาสตร์เชิงคำศัพท์ โดยเฉพาะอย่างยิ่งเมื่อนำไปใช้กับคอมพิวเตอร์ การจำลองความหมายของคำจะง่ายขึ้นเมื่อเข้าใจคำที่กำหนดในแง่ของคำที่เกี่ยวข้อง ดังนั้น เครือข่ายความหมายจึงมีความสำคัญในภาษาศาสตร์เชิงคำนวณอย่างไรก็ตาม วิธีการอื่นๆ ในด้านสัทวิทยา (เช่นทฤษฎีความเหมาะสมที่สุดซึ่งใช้กราฟแบบแลตติส ) และสัณฐานวิทยา (เช่น สัณฐานวิทยาแบบสถานะจำกัด โดยใช้ตัวแปลงสัญญาณแบบสถานะจำกัด ) ก็เป็นที่นิยมในการวิเคราะห์ภาษาในฐานะกราฟเช่นกัน อันที่จริง ประโยชน์ของคณิตศาสตร์สาขานี้ต่อภาษาศาสตร์ได้ก่อให้เกิดองค์กรต่างๆ เช่นTextGraphsรวมถึงโครงการ 'Net' ต่างๆ เช่นWordNet , VerbNetและอื่นๆ

ทฤษฎีกราฟยังใช้ในการศึกษาโมเลกุลในวิชาเคมีและฟิสิกส์ในฟิสิกส์สสารควบแน่นโครงสร้างสามมิติของโครงสร้างอะตอมจำลองที่ซับซ้อนสามารถศึกษาได้ในเชิงปริมาณโดยการรวบรวมสถิติเกี่ยวกับคุณสมบัติทางทฤษฎีกราฟที่เกี่ยวข้องกับโทโพโลยีของอะตอม นอกจากนี้ “ กราฟของเฟย์นแมนและกฎการคำนวณสรุปทฤษฎีสนามควอนตัมในรูปแบบที่ใกล้เคียงกับตัวเลขการทดลองที่ต้องการทำความเข้าใจ” ^{[ 65 ]}ในวิชาเคมี กราฟเป็นแบบจำลองที่เป็นธรรมชาติสำหรับโมเลกุล โดยที่จุดยอดแทนอะตอมและขอบแทนพันธะวิธีการนี้ใช้โดยเฉพาะอย่างยิ่งในการประมวลผลโครงสร้างโมเลกุลด้วยคอมพิวเตอร์ ตั้งแต่โปรแกรมแก้ไขทางเคมีไปจนถึงการค้นหาฐานข้อมูล ในฟิสิกส์เชิงสถิติกราฟสามารถแสดงถึงการเชื่อมต่อในท้องถิ่นระหว่างส่วนที่โต้ตอบกันของระบบ ตลอดจนพลวัตของกระบวนการทางกายภาพบนระบบดังกล่าว ในทำนองเดียวกัน ในประสาทวิทยาเชิงคำนวณกราฟสามารถใช้เพื่อแสดงการเชื่อมต่อการทำงานระหว่างบริเวณสมองที่โต้ตอบกันเพื่อให้เกิดกระบวนการทางปัญญาต่างๆ โดยที่จุดยอดแทนบริเวณต่างๆ ของสมอง และขอบแทนการเชื่อมต่อระหว่างบริเวณเหล่านั้น ทฤษฎีกราฟมีบทบาทสำคัญในการสร้างแบบจำลองทางไฟฟ้าของเครือข่ายไฟฟ้า โดยที่น้ำหนักจะสัมพันธ์กับความต้านทานของส่วนสายไฟเพื่อให้ได้คุณสมบัติทางไฟฟ้าของโครงสร้างเครือข่าย^{[ 66 ]}กราฟยังใช้เพื่อแสดงช่องขนาดเล็กของตัวกลางที่มีรูพรุนโดยที่จุดยอดแทนรูพรุน และขอบแทนช่องขนาดเล็กที่เชื่อมต่อรูพรุนทฤษฎีกราฟทางเคมีใช้กราฟโมเลกุลเป็นวิธีการสร้างแบบจำลองโมเลกุล กราฟและเครือข่ายเป็นแบบจำลองที่ยอดเยี่ยมในการศึกษาและทำความเข้าใจการเปลี่ยนเฟสและปรากฏการณ์วิกฤต การลบโหนดหรือขอบนำไปสู่การเปลี่ยนผ่านวิกฤตที่เครือข่ายแตกออกเป็นกลุ่มเล็กๆ ซึ่งศึกษาเป็นการเปลี่ยนเฟส การแตกนี้ศึกษาผ่านทฤษฎีการซึมผ่าน^{[ 67 ]}

ทฤษฎีกราฟยังถูกนำมาใช้กันอย่างแพร่หลายในสังคมวิทยาเช่น เพื่อวัดชื่อเสียงของนักแสดงหรือเพื่อสำรวจการแพร่กระจายข่าวลือโดยเฉพาะอย่างยิ่งผ่านการใช้ ซอฟต์แวร์ วิเคราะห์เครือข่ายสังคมภายใต้ร่มเงาของเครือข่ายสังคมมีกราฟหลายประเภทที่แตกต่างกัน^{[ 69 ]}กราฟความรู้จักและมิตรภาพอธิบายว่าผู้คนรู้จักกันหรือไม่ กราฟอิทธิพลจำลองว่าบุคคลบางคนสามารถมีอิทธิพลต่อพฤติกรรมของผู้อื่นได้หรือไม่ สุดท้าย กราฟความร่วมมือจำลองว่าคนสองคนทำงานร่วมกันในลักษณะใดลักษณะหนึ่ง เช่น การแสดงภาพยนตร์ด้วยกัน

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

กราฟยังถูกใช้กันอย่างแพร่หลายในชีววิทยาโมเลกุลและจีโนมิกส์เพื่อสร้างแบบจำลองและวิเคราะห์ชุดข้อมูลที่มีความสัมพันธ์ที่ซับซ้อน ตัวอย่างเช่น วิธีการที่ใช้กราฟมักใช้เพื่อ 'จัดกลุ่ม' เซลล์เข้าด้วยกันเป็นประเภทเซลล์ในการวิเคราะห์ทรานสคริปโตมของเซลล์เดี่ยวการใช้งานอีกอย่างหนึ่งคือการสร้างแบบจำลองยีนหรือโปรตีนในวิถีและศึกษาความสัมพันธ์ระหว่างกัน เช่น วิถีการเผาผลาญและเครือข่ายควบคุมยีน^{[ 70 ]}ต้นไม้แห่งวิวัฒนาการ เครือข่ายนิเวศวิทยา และการจัดกลุ่มแบบลำดับชั้นของรูปแบบการแสดงออกของยีนก็แสดงเป็นโครงสร้างกราฟเช่นกัน

ทฤษฎีกราฟยังใช้ในคอนเน็กโทมิกส์ด้วย^{[ 71 ]}ระบบประสาทสามารถมองได้ว่าเป็นกราฟ โดยที่โหนดคือเซลล์ประสาทและขอบคือการเชื่อมต่อระหว่างเซลล์ประสาทเหล่านั้น

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

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

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

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

งานบุกเบิกของWT Tutteมีอิทธิพลอย่างมากต่อเรื่องการวาดกราฟ หนึ่งในความสำเร็จที่สำคัญของเขาคือการนำวิธีการทางพีชคณิตเชิงเส้นมาใช้ในการวาดกราฟ

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

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

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

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

โครงสร้างเมทริกซ์ประกอบด้วยเมทริกซ์เหตุการณ์ (incidence matrix)ซึ่งเป็นเมทริกซ์ที่มีค่า 0 และ 1 โดยแถวแทนจุดยอดและคอลัมน์แทนขอบ และเมทริกซ์ประชิด (adjacency matrix ) ซึ่งทั้งแถวและคอลัมน์มีค่าดัชนีเป็นจุดยอด ในทั้งสองกรณี ค่า 1 แสดงถึงวัตถุสองชิ้นที่อยู่ติดกัน และค่า 0 แสดงถึงวัตถุสองชิ้นที่ไม่ติดกันเมทริกซ์ดีกรี (degree matrix)แสดงถึงดีกรีของจุดยอด เมทริก ซ์ลาปลาเซียน (Laplacian matrix)เป็นรูปแบบที่ดัดแปลงมาจากเมทริกซ์ประชิดที่รวมข้อมูลเกี่ยวกับดีกรีของจุดยอด และมีประโยชน์ในการคำนวณบางอย่าง เช่นทฤษฎีบทของเคิร์ชฮอฟฟ์เกี่ยวกับจำนวนต้นไม้แผ่คลุมของกราฟ เมทริกซ์ระยะทาง (distance matrix ) เช่นเดียวกับเมทริกซ์ประชิด มีทั้งแถวและคอลัมน์ที่มีค่าดัชนีเป็นจุดยอด แต่แทนที่จะมีค่า 0 หรือ 1 ในแต่ละเซลล์ มันจะมีค่าความยาวของเส้นทางที่สั้นที่สุดระหว่างจุดยอดสองจุด

มีงานวิจัยจำนวนมากเกี่ยวกับการนับกราฟที่ตรงตามเงื่อนไขที่กำหนด งานวิจัยบางส่วนนี้พบได้ใน Harary และ Palmer (1973)

ปัญหาทั่วไปอย่างหนึ่งที่เรียกว่าปัญหาไอโซมอร์ฟิซึมของกราฟย่อยคือ การหากราฟที่กำหนดไว้เป็นกราฟย่อยในกราฟที่กำหนดให้ เหตุผลหนึ่งที่น่าสนใจในคำถามนี้คือคุณสมบัติของกราฟ หลายอย่าง สามารถถ่ายทอดไปยังกราฟย่อยได้ ซึ่งหมายความว่ากราฟจะมีคุณสมบัตินั้นก็ต่อเมื่อกราฟย่อยทั้งหมดมีคุณสมบัตินั้นด้วย การหากราฟย่อยที่ใหญ่ที่สุดของชนิดใดชนิดหนึ่งมักเป็นปัญหา NP-completeตัวอย่างเช่น:

• การค้นหากราฟย่อยสมบูรณ์ที่ใหญ่ที่สุดเรียกว่าปัญหาคลิก (NP-complete)

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

ปัญหาที่คล้ายกันคือการหาซับกราฟแบบเหนี่ยวนำในกราฟที่กำหนดให้ อีกครั้งหนึ่ง คุณสมบัติสำคัญบางอย่างของกราฟจะสืบทอดไปยังซับกราฟแบบเหนี่ยวนำ ซึ่งหมายความว่ากราฟจะมีคุณสมบัติก็ต่อเมื่อซับกราฟแบบเหนี่ยวนำทั้งหมดมีคุณสมบัตินั้นด้วย การหาซับกราฟแบบเหนี่ยวนำที่ใหญ่ที่สุดของชนิดใดชนิดหนึ่งก็มักจะเป็นปัญหา NP-complete เช่นกัน ตัวอย่างเช่น:

• การค้นหาซับกราฟเหนี่ยวนำที่ไม่มีขอบที่ใหญ่ที่สุดหรือเซตอิสระที่ ใหญ่ที่สุด เรียกว่าปัญหาเซตอิสระ (NP-complete)

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

• กราฟจะเป็นกราฟระนาบได้ ก็ ต่อเมื่อกราฟไมเนอร์ของมันไม่มีทั้งกราฟสองส่วนสมบูรณ์K _3,3 (ดูปัญหาบ้านสามหลัง ) และกราฟสมบูรณ์K ₅

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

• กราฟจะเป็นกราฟระนาบได้ก็ต่อเมื่อไม่มีกราฟสองส่วนสมบูรณ์K _3,3หรือกราฟสมบูรณ์K ₅ เป็นส่วน ย่อย

อีกปัญหาหนึ่งในเรื่องการบรรจุของส่วนย่อยคือสมมติฐานของเคลแมนส์-เซย์มัวร์ :

• กราฟ ที่เชื่อมต่อกันด้วย 5 จุดยอดทุกกราฟที่ไม่ใช่กราฟระนาบจะมีการแบ่งย่อย ของ กราฟสมบูรณ์ 5 จุดยอดK ₅

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

• สมมติฐานการสร้างใหม่

ปัญหาและทฤษฎีบทมากมายในทฤษฎีกราฟเกี่ยวข้องกับวิธีการระบายสีกราฟแบบต่างๆ โดยทั่วไปแล้ว เรามักสนใจการระบายสีกราฟโดยที่ไม่มีจุดยอดที่อยู่ติดกันสองจุดใดมีสีเดียวกัน หรือมีข้อจำกัดอื่นๆ ที่คล้ายคลึงกัน นอกจากนี้ เราอาจพิจารณาการระบายสีขอบ (โดยที่ไม่มีขอบสองเส้นใดทับกันมีสีเดียวกัน) หรือรูปแบบอื่นๆ ผลลัพธ์และข้อสันนิษฐานที่มีชื่อเสียงเกี่ยวกับการระบายสีกราฟ ได้แก่:

• ทฤษฎีสี่สี
• ทฤษฎีกราฟสมบูรณ์แบบที่แข็งแกร่ง
• การคาดเดาของแอร์ดอส–ฟาเบอร์–โลวาสซ์
• สมมติฐานการระบายสีทั้งหมดหรือที่เรียกว่าสมมติฐานของเบห์ซาด (ยังไม่สามารถหาคำตอบได้)
• ข้อสันนิษฐานเกี่ยวกับการระบายสีรายการ (ยังไม่ได้รับการแก้ไข)
• สมมติฐานของ Hadwiger (ทฤษฎีกราฟ) (ยังไม่ได้รับการแก้ไข)

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

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

• ปัญหาเส้นทางแฮมิลโทเนียน
• ต้นไม้เชื่อมโยงขั้นต่ำ
• ปัญหาการตรวจสอบเส้นทาง (หรือเรียกอีกอย่างว่า "ปัญหาบุรุษไปรษณีย์ชาวจีน")
• สะพานเจ็ดแห่งของเมืองเคอนิกส์เบิร์ก
• ปัญหาเส้นทางที่สั้นที่สุด
• ต้นไม้สไตเนอร์
• ปัญหาบ้านสามหลัง
• ปัญหาพนักงานขายเดินทาง (NP-hard)

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

• ทฤษฎีการไหลสูงสุด การตัดต่ำสุด

• ปัญหาเจ้าหน้าที่รักษาความปลอดภัยพิพิธภัณฑ์

ปัญหาการครอบคลุมในกราฟอาจหมายถึงปัญหาการครอบคลุมเซต ต่างๆ บนเซตย่อยของจุดยอด/กราฟย่อย

• ปัญหา เซตครอบงำ (Dominating set problem) เป็นกรณีพิเศษของปัญหาเซตปกคลุม (Set cover problem) โดยที่เซตเหล่านั้นคือย่านใกล้เคียง แบบปิด (closed neighborhoods )
• ปัญหาการคลุมจุดยอด (Vertex cover problem)เป็นกรณีพิเศษของปัญหาการคลุมเซต (Set cover problem) โดยที่เซตที่จะคลุมคือขอบทุกเส้น
• ปัญหาการครอบคลุมเซตดั้งเดิม หรือที่เรียกว่าเซตกระทบ สามารถอธิบายได้ว่าเป็นปัญหาการครอบคลุมจุดยอดในไฮเปอร์กราฟ

การแยกส่วน (Decomposition) ซึ่งนิยามว่าเป็นการแบ่งเซตของขอบของกราฟ (โดยมีจำนวนจุดยอดที่จำเป็นควบคู่ไปกับขอบของแต่ละส่วนของการแบ่งส่วน) มีคำถามหลากหลายประเภท บ่อยครั้ง ปัญหาคือการแยกส่วนกราฟออกเป็นกราฟย่อยที่สมมาตรกับกราฟที่กำหนดไว้ ตัวอย่างเช่น การแยกส่วนกราฟสมบูรณ์ออกเป็นวัฏจักรแฮมิลโทเนียน ปัญหาอื่นๆ อาจระบุตระกูลของกราฟที่ควรแยกส่วนจากกราฟที่กำหนด ตัวอย่างเช่น ตระกูลของวัฏจักร หรือการแยกส่วนกราฟสมบูรณ์K _nออกเป็น ต้นไม้ที่กำหนดไว้ n − 1 ต้น ซึ่งมี จำนวนขอบ 1, 2, 3, ..., n − 1 ตามลำดับ

ปัญหาการแยกส่วนประกอบเฉพาะบางปัญหาและปัญหาที่คล้ายคลึงกันที่ได้รับการศึกษา ได้แก่:

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

โจทย์หลายข้อเกี่ยวข้องกับการระบุลักษณะเฉพาะของสมาชิกในกราฟประเภทต่างๆ ตัวอย่างของคำถามดังกล่าวมีดังต่อไปนี้:

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

• แกลเลอรีของกราฟที่มีชื่อ
• คำศัพท์เฉพาะทางทฤษฎีกราฟ
• รายชื่อหัวข้อทฤษฎีกราฟ
• รายชื่อปัญหาที่ยังแก้ไม่ตกในทฤษฎีกราฟ
• สิ่งพิมพ์ในทฤษฎีกราฟ
• อัลกอริทึมกราฟ
• นักทฤษฎีกราฟ

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับทฤษฎีกราฟ

• "ทฤษฎีกราฟ" , สารานุกรมคณิตศาสตร์ , EMS Press , 2001 [1994]
• บทเรียนทฤษฎีกราฟ(เก็บถาวรเมื่อ 2012-01-16 ที่Wayback Machine)
• ฐานข้อมูลที่สามารถค้นหาได้ของกราฟเชื่อมต่อขนาดเล็ก
• House of Graphs — ฐานข้อมูลกราฟที่สามารถค้นหาได้ พร้อมฟีเจอร์การค้นหาโดยใช้ภาพวาด
• แกลเลอรีรูปภาพ: กราฟจากWayback Machine (เก็บถาวรเมื่อวันที่ 6 กุมภาพันธ์ 2549)
• รายการแหล่งข้อมูลทฤษฎีกราฟฉบับย่อพร้อมคำอธิบายสำหรับนักวิจัย
• rocs — IDE สำหรับทฤษฎีกราฟ
• ชีวิตทางสังคมของเราเตอร์ — บทความที่ไม่เน้นด้านเทคนิคที่กล่าวถึงกราฟแสดงความสัมพันธ์ระหว่างคนกับคอมพิวเตอร์
• ซอฟต์แวร์ทฤษฎีกราฟ — เครื่องมือสำหรับการสอนและการเรียนรู้ทฤษฎีกราฟ
• หนังสือออนไลน์และแหล่งข้อมูลในห้องสมุดของคุณและห้องสมุดอื่นๆเกี่ยวกับทฤษฎีกราฟ
• รายชื่ออัลกอริธึมกราฟที่เก็บถาวรไว้เมื่อวันที่ 13 กรกฎาคม 2019 ในWayback Machineพร้อมข้อมูลอ้างอิงและลิงก์ไปยังไลบรารีการใช้งานกราฟ

• Hartmann, Alexander K.; Weigt, Martin (2005). "บทนำเกี่ยวกับกราฟ" การเปลี่ยนเฟสในปัญหาการหาค่าเหมาะสมเชิงการจัดเรียง: พื้นฐาน อัลกอริทึม และกลศาสตร์สถิติ Wiley. หน้า  25–66 . arXiv : cond-mat/0602129 . doi : 10.1002/3527606734.ch3 . ISBN 978-3-527-60673-3.
• หนังสือ Digraphs: Theory Algorithms and Applications 2007 โดย Jorgen Bang-Jensen และ Gregory Gutin
• ทฤษฎีกราฟ โดย ไรน์ฮาร์ด ดีสเตล