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

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

ในการศึกษาปัญหาสำคัญและยากต่างๆ ในทฤษฎีกราฟ (เช่น สมมติฐานการ ครอบคลุมสองเท่าของวัฏจักรและสมมติฐานการไหล 5 ) จะพบกราฟประเภทหนึ่งที่น่าสนใจแต่ค่อนข้างลึกลับเรียกว่า snarks แม้จะมีคำจำกัดความที่เรียบง่าย...และมีการศึกษามานานกว่าศตวรรษ คุณสมบัติและโครงสร้างของพวกมันก็ยังไม่เป็นที่รู้จักมากนัก^{[ 1 ]}

นอกจากปัญหาที่พวกเขากล่าวถึงแล้วข้อสันนิษฐานเรื่อง snarkของWT Tutteยังเกี่ยวข้องกับการมีอยู่ของกราฟ Petersenในฐานะกราฟย่อยของ snark ซึ่งมีการประกาศการพิสูจน์มานานแล้วแต่ยังไม่ได้ตีพิมพ์ และจะยุติกรณีพิเศษของการมีอยู่ของ4-flow ที่ไม่มีที่ใดเป็นศูนย์

กราฟ Snark ได้รับการตั้งชื่อโดยนักคณิตศาสตร์ชาวอเมริกันMartin Gardnerในปี 1976 ตามชื่อวัตถุลึกลับและหาได้ยากในบทกวีเรื่องThe Hunting of the SnarkโดยLewis Carroll [ ^{2 ] อย่างไรก็ตาม}การศึกษากราฟประเภทนี้มีอายุเก่าแก่กว่าชื่อของมันมากPeter G. Taitเริ่มต้นการศึกษากราฟ Snark ในปี 1880 เมื่อเขาพิสูจน์ว่าทฤษฎีบทสี่สีเทียบเท่ากับข้อความที่ว่าไม่มีกราฟ Snark ใดเป็นระนาบ[ ^{3 ] กราฟ} แรกที่ทราบว่าเป็นกราฟ Snark คือกราฟ Petersenซึ่งได้รับการพิสูจน์ว่าเป็นกราฟ Snark โดยJulius Petersenในปี 1898 ^{[ 4 ]}แม้ว่ามันจะเคยได้รับการศึกษาเพื่อวัตถุประสงค์อื่นโดยAlfred Kempeในปี 1886 มาแล้วก็ตาม ^{[ 5 ]}

สแนร์คอีกสี่ตัวที่รู้จักกันคือ

• หนามแหลม Blanuša (สองอันมี 18 จุดยอด) ค้นพบโดยDanilo Blanušaในปี พ.ศ. 2489 ^{[ 6 ]}
• หนามเดส์การ์ต (210 จุดยอด) ที่ค้นพบโดยBill Tutteในปี พ.ศ. 2491 ^{[ 7 ]}และ
• Szekeres snark (50 จุดยอด) ค้นพบโดย^George Szekeresใน^ปี1973

ในปี พ.ศ. 2518 รูฟัส ไอแซคส์ได้ขยายวิธีการของบลานูชาเพื่อสร้างสนาร์คสองตระกูลอนันต์ ได้แก่สนาร์คดอกไม้และสนาร์คบลานูชา-เดส์การ์ต -เซเกเรส ซึ่งเป็นตระกูลที่รวมสนาร์คบลานูชาสองแบบ สนาร์ คเดส์การ์ตและสนาร์คเซเกเรส ไอแซคส์ยังค้นพบสนาร์ค 30 จุดยอดที่ไม่จัดอยู่ในตระกูลบลานูชา-เดส์การ์ต-เซเกเรส และไม่ใช่สนาร์คดอกไม้ นั่นคือ สนา ร์คดาวคู่^{[ 9 ]}อีกตระกูลอนันต์หนึ่ง คือ สนา ร์คของลูเพคีน ได้รับการตีพิมพ์โดยไอแซคส์ในปี พ.ศ. 2519 โดยให้เครดิตแก่ เอฟ. ลูเพคีน ซึ่งรวมถึงสนาร์ค 22 จุดยอดสองแบบที่ได้มาจากกราฟปีเตอร์เซน^{[ 10 ]}สนาร์ควัตกินส์ 50 จุดยอดถูกค้นพบในปี พ.ศ. 2532 ^{[ 11 ]}

กราฟลูกบาศก์ที่ไม่สามารถระบายสีขอบได้สามสีที่น่าสนใจอีกกราฟหนึ่งคือกราฟของ Tietzeซึ่งมี 12 จุดยอด ดังที่Heinrich Franz Friedrich Tietzeค้นพบในปี 1910 กราฟนี้เป็นขอบเขตของการแบ่งย่อยของแถบโมเบียสที่ต้องใช้หกสี^{[ 12 ]}อย่างไรก็ตาม เนื่องจากมีรูปสามเหลี่ยมอยู่ด้วย จึงโดยทั่วไปแล้วไม่ถือว่าเป็น snark ตามคำจำกัดความที่เข้มงวดของ snark กราฟ snark ที่เล็กที่สุดคือกราฟ Petersen และ snark ของ Blanuša ตามด้วย snark 20 จุดยอดที่แตกต่างกันหกแบบ^{[ 13 ]}

รายการ snark ทั้งหมดที่มีจุดยอดไม่เกิน 36 จุด (ตามคำจำกัดความที่เข้มงวด) และไม่เกิน 34 จุด (ตามคำจำกัดความที่อ่อนกว่า) ถูกสร้างขึ้นโดย Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund และ Klas Markström ในปี 2012 ^{[ 13 ]}จำนวน snark สำหรับจำนวนจุดยอดคู่ที่กำหนดจะเพิ่มขึ้นอย่างน้อยแบบเลขชี้กำลังตามจำนวนจุดยอด^{[ 14 ]} (เนื่องจากมีจุดยอดที่มีดีกรีคี่ snark ทั้งหมดจึงต้องมีจำนวนจุดยอดคู่ตามเลมมาการจับมือ ) ^{[ 15 ]} ลำดับOEIS A130315ประกอบด้วยจำนวน snark ที่ไม่ใช่จุดยอดธรรมดาสำหรับค่าเล็กๆของ^{[ 16 ]}${\displaystyle 2n}$${\displaystyle n}$

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

• ถ้ากราฟลูกบาศก์มีสะพานซึ่งเป็นขอบที่หากลบออกจะทำให้ขาดการเชื่อมต่อ กราฟนั้นจะไม่สามารถเป็นกราฟชั้นหนึ่งได้ ตามทฤษฎีบทการจับมือกราฟย่อยที่อยู่ทั้งสองด้านของสะพานจะมีจำนวนจุดยอดเป็นเลขคี่ ไม่ว่าจะเลือกสีใดในสามสีสำหรับสะพาน จำนวนจุดยอดที่เป็นเลขคี่ของกราฟย่อยเหล่านี้จะป้องกันไม่ให้กราฟย่อยเหล่านี้ถูกปกคลุมด้วยวัฏจักรที่สลับกันระหว่างสองสีที่เหลือ ซึ่งจำเป็นในกรณีการระบายสีขอบ 3 สี ด้วยเหตุนี้ โดยทั่วไปแล้ว snarks จะต้องไม่มีสะพาน^{[ 2 ] [ 9 ]}
• ลูป (ขอบที่เชื่อมจุดยอดกับตัวเอง) ไม่สามารถระบายสีได้โดยไม่ทำให้สีเดียวกันปรากฏซ้ำสองครั้งที่จุดยอดนั้น ซึ่งเป็นการละเมิดข้อกำหนดปกติสำหรับการระบายสีขอบกราฟ นอกจากนี้ วงจรที่ประกอบด้วยจุดยอดสองจุดที่เชื่อมต่อกันด้วยขอบสองเส้น สามารถแทนที่ด้วยขอบเส้นเดียวที่เชื่อมจุดยอดข้างเคียงอีกสองจุดได้เสมอ ทำให้กราฟง่ายขึ้นโดยไม่เปลี่ยนแปลงความสามารถในการระบายสีขอบสามเส้น ด้วยเหตุผลเหล่านี้ snarks จึงมักถูกจำกัดไว้เฉพาะกราฟแบบง่ายกราฟที่ไม่มีลูปหรือการเชื่อมต่อหลายจุด^{[ 9 ]}
• ถ้ากราฟมีรูปสามเหลี่ยม ก็สามารถลดรูปกราฟนั้นได้อีกครั้งโดยไม่เปลี่ยนแปลงความสามารถในการระบายสีขอบสามด้าน โดยการยุบจุดยอดทั้งสามของรูปสามเหลี่ยมให้เป็นจุดยอดเดียว ดังนั้น นิยามของ snark หลายๆ นิยามจึงห้ามใช้รูปสามเหลี่ยม^{[ 9 ]}อย่างไรก็ตาม แม้ว่าข้อกำหนดนี้จะระบุไว้ในงานของ Gardner ที่ให้ชื่อ "snark" แก่กราฟเหล่านี้ แต่ Gardner ก็ระบุกราฟของ Tietzeซึ่งมีรูปสามเหลี่ยมอยู่ด้วยว่าเป็น snark ^{[ 2 ]}
• หากกราฟมีวงจรสี่จุดยอด สามารถลดรูปได้สองวิธีที่แตกต่างกัน โดยการลบขอบตรงข้ามสองขอบของวงจรออก และแทนที่เส้นทางที่ได้ของจุดยอดดีกรีสองด้วยขอบเดี่ยว กราฟจะมีสีขอบสามสีก็ต่อเมื่อการลดรูปอย่างน้อยหนึ่งวิธีนี้ทำได้ ดังนั้น Isaacs จึงต้องการกราฟลูกบาศก์คลาสสองที่ "ไม่ธรรมดา" เพื่อหลีกเลี่ยงวงจรสี่จุดยอด^{[ 9 ]}และผู้เขียนคนอื่นๆ ก็ได้ปฏิบัติตามในการห้ามวงจรเหล่านี้^{[ 13 ]}ข้อกำหนดที่ว่า snark ต้องหลีกเลี่ยงวงจรที่มีความยาวสี่หรือน้อยกว่านั้น สามารถสรุปได้โดยการระบุว่าเส้นรอบวงของกราฟเหล่านี้ ความยาวของวงจรที่สั้นที่สุด ต้องมีอย่างน้อยห้า
• ยิ่งไปกว่านั้น คำจำกัดความที่ใช้โดยBrinkmann et al. (2012)กำหนดให้ snark ต้องมีขอบเชื่อมต่อแบบวนรอบ 4 ขอบ นั่นหมายความว่าต้องไม่มีเซตย่อยที่มีขอบสามขอบหรือน้อยกว่า ซึ่งการลบขอบเหล่านั้นจะทำให้กราฟแยกออกเป็นสองกราฟย่อย โดยแต่ละกราฟย่อยจะมีอย่างน้อยหนึ่งวงจร Brinkmann et al. กำหนดให้ snark เป็นกราฟลูกบาศก์ที่มีขอบเชื่อมต่อแบบวนรอบ 4 ขอบ มีเส้นรอบวงห้าหรือมากกว่า และคลาสสอง พวกเขากำหนด "snark แบบอ่อน" ให้สามารถมีเส้นรอบวงสี่ได้^{[ 13 ]}

แม้ว่าคำจำกัดความเหล่านี้จะพิจารณาเฉพาะข้อจำกัดเกี่ยวกับเส้นรอบวงไม่เกินห้า แต่งูที่มีเส้นรอบวงใหญ่ตามอำเภอใจก็มีอยู่^{[ 17 ]}

งานของ Peter G. Tait ได้พิสูจน์ว่าทฤษฎีบทสี่สีเป็นจริงก็ต่อเมื่อ snark ทุกตัวไม่ใช่ระนาบ^{[ 3 ]}ทฤษฎีบทนี้ระบุว่ากราฟระนาบทุกตัวมีการระบายสีกราฟของจุดยอดด้วยสี่สี แต่ Tait ได้แสดงวิธีการแปลงการระบายสีจุดยอด 4 สีให้กับกราฟระนาบสูงสุดให้เป็นการระบายสีขอบ 3 สีให้กับกราฟคู่ ของมัน ซึ่งเป็นกราฟลูกบาศก์และกราฟระนาบ และในทางกลับกัน ดังนั้น snark ระนาบจึงจำเป็นต้องเป็นคู่ของตัวอย่างค้านของทฤษฎีบทสี่สี ดังนั้น การพิสูจน์ทฤษฎีบทสี่สีในภายหลัง^{[ 18 ]}จึงแสดงให้เห็นว่า snark ทั้งหมดไม่ใช่ระนาบ^{[ 19 ]}

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

ข้อสันนิษฐานเรื่องการครอบคลุมสองชั้นของวงจรระบุว่า ในกราฟที่ไม่มีสะพานทุกกราฟ เราสามารถหาชุดของวงจรที่ครอบคลุมขอบแต่ละขอบสองครั้ง หรือเทียบเท่ากับว่ากราฟสามารถฝังลงบนพื้นผิวได้ในลักษณะที่ทุกหน้าของการฝังเป็นวงจรแบบง่าย เมื่อกราฟลูกบาศก์มีการระบายสีขอบ 3 สี กราฟนั้นจะมีการครอบคลุมสองชั้นของวงจรซึ่งประกอบด้วยวงจรที่เกิดจากสีแต่ละคู่ ดังนั้น ในบรรดากราฟลูกบาศก์ กราฟ snark จึงเป็นตัวอย่างค้านที่เป็นไปได้เพียงอย่างเดียว โดยทั่วไปแล้ว กราฟ snark เป็นกรณีที่ยากสำหรับข้อสันนิษฐานนี้: หากเป็นจริงสำหรับกราฟ snark ก็จะเป็นจริงสำหรับกราฟทั้งหมด^{[ 21 ]}ในเรื่องนี้Branko Grünbaumตั้งข้อสันนิษฐานว่าไม่มีกราฟ snark ใดที่สามารถฝังลงบนพื้นผิวได้ในลักษณะที่ทุกหน้าเป็นวงจรแบบง่าย และทุกสองหน้าจะไม่ทับซ้อนกันหรือมีขอบร่วมกันเพียงขอบเดียว หากกราฟ snark ใดมีการฝังแบบนั้น หน้าของมันจะก่อให้เกิดการครอบคลุมสองชั้นของวงจร อย่างไรก็ตาม Martin Kochol ได้ค้นพบตัวอย่างค้านต่อสมมติฐานของ Grünbaum ^{[ 22 ]}

การพิจารณาว่ากราฟลูกบาศก์ที่เชื่อมต่อแบบวนรอบ 5 เส้นที่กำหนดนั้นสามารถระบายสีขอบได้ 3 สีหรือไม่นั้นเป็นปัญหาNP-completeดังนั้น การพิจารณาว่ากราฟเป็น snark หรือไม่จึงเป็นปัญหาco-NP- complete ^{[ 23 ]}

WT Tutteตั้งข้อสันนิษฐานว่า snark ทุกอันมีกราฟ Petersen เป็นminorนั่นคือ เขาตั้งข้อสันนิษฐานว่า snark ที่เล็กที่สุด กราฟ Petersen อาจถูกสร้างขึ้นจาก snark อื่นๆ โดยการยุบขอบบางส่วนและลบขอบอื่นๆ ออก หรือเทียบเท่า (เนื่องจากกราฟ Petersen มีดีกรีสูงสุดสาม) snark ทุกอันมี subgraph ที่สามารถสร้างขึ้นจากกราฟ Petersen โดยการแบ่งขอบบางส่วนข้อสันนิษฐานนี้เป็นรูปแบบที่แข็งแกร่งขึ้นของทฤษฎีบทสี่สีเนื่องจากกราฟใดๆ ที่มีกราฟ Petersen เป็น minor จะต้องไม่ใช่กราฟระนาบ ในปี 1999 Neil Robertson , Daniel P. Sanders , Paul SeymourและRobin Thomasได้ประกาศการพิสูจน์ข้อสันนิษฐานนี้^{[ 24 ]}ขั้นตอนต่างๆ ที่นำไปสู่ผลลัพธ์นี้ได้รับการตีพิมพ์ในปี 2016 และ 2019 ^{[ 25 ] [ 26 ]}แต่การพิสูจน์ที่สมบูรณ์ยังไม่ได้รับการตีพิมพ์^{[ 19 ]}ดูสมมติฐานของ Hadwigerสำหรับปัญหาและผลลัพธ์อื่นๆ ที่เกี่ยวข้องกับการระบายสีกราฟกับไมเนอร์กราฟ

Tutte ยังตั้งข้อสันนิษฐานถึงการวางนัยทั่วไปสำหรับกราฟใดๆ อีกด้วย: กราฟที่ไม่มีสะพานทุกกราฟที่ไม่มี Petersen minor จะมี4-flow ที่ไม่มีที่ใดเป็นศูนย์นั่นคือ ขอบของกราฟอาจถูกกำหนดทิศทางและตัวเลขจากเซต {1, 2, 3} โดยที่ผลรวมของตัวเลขขาเข้าลบด้วยผลรวมของตัวเลขขาออกที่แต่ละจุดยอดหารด้วยสี่ลงตัว ดังที่ Tutte แสดงให้เห็น สำหรับกราฟลูกบาศก์ การกำหนดดังกล่าวจะมีอยู่ก็ต่อเมื่อขอบสามารถระบายสีได้ด้วยสามสี ดังนั้นข้อสันนิษฐานจึงเป็นผลมาจากข้อสันนิษฐาน snark ในกรณีนี้ อย่างไรก็ตาม การพิสูจน์ข้อสันนิษฐาน snark จะไม่สามารถแก้ปัญหาเรื่องการมีอยู่ของ 4-flow สำหรับกราฟที่ไม่ใช่ลูกบาศก์ได้^{[ 27 ]}

• เดส์การ์ตส์ ประชดประชัน
• มุกตลกสองดาว
• สเนคเคเรส
• วาตกินส์พูดประชด

• Blanuša พูดจาเสียดสี
• ดอกไม้ที่เสียดสี
• ลูเพคิน สแนร์ค

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

• ไวส์สไตน์, เอริค ดับเบิลยู. , "เสียดสี" , แมธเวิลด์