ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
ในคณิตศาสตร์และวิทยาการคอมพิวเตอร์ กราฟ (อังกฤษ: Graph) ประกอบไปด้วยเซตของวัตถุที่เรียกว่าจุดยอด (vertex) ซึ่งเชื่อมต่อกันด้วยเส้นเชื่อม (edge) โดยทั่วไปแล้วเรามักวาดรูปแสดงกราฟโดยใช้จุด (แทนจุดยอด) เชื่อมกันด้วยเส้น (แทนเส้นเชื่อม) กราฟเป็นวัตถุพื้นฐานของการศึกษาในวิยุตคณิต หัวข้อทฤษฎีกราฟ
เส้นเชื่อมอาจมีทิศทางหรือไม่ก็ได้ ตัวอย่างเช่น สมมุติให้จุดยอดแทนคนและเส้นเชื่อมแทนการจับมือกัน เส้นเชื่อมก็จะเป็นเส้นเชื่อมไม่มีทิศ เพราะการที่ A จับมือ B ก็แปลว่า B จับมือ A อย่างไรก็ตาม สมมุติถ้าจุดยอดแทนคนและเส้นเชื่อมแทนการรู้จัก เส้นเชื่อมก็ต้องเป็นเส้นเชื่อมมีทิศทาง เพราะ A รู้จัก B ไม่จำเป็นว่า B ต้องรู้จัก A หรือนั่นก็คือความสัมพันธ์การรู้จักไม่เป็น
จุดยอดอาจจะถูกเรียกว่าโหนด ปม หรือจุด ในขณะที่เส้นเชื่อมอาจถูกเรียกว่าเส้น คำว่า "กราฟ" ถูกใช้ครั้งแรกโดย ในปี พ.ศ. 2421
นิยาม
โดยทั่วไปกราฟ G คือคู่อันดับ G = (V, E) โดยที่ V คือเซตของจุดยอด และ E คือเซตของเส้นเชื่อมซึ่งเป็นคู่ไม่อันดับของจุดยอด อันที่จริงนิยามที่กล่าวไปเป็นเพียงประเภทหนึ่งของกราฟที่เรียกว่า กราฟไม่ระบุทิศทาง และเป็น กราฟอย่างง่าย
กราฟประเภทอื่นๆจะมีรายละเอียดของเซตเส้นเชื่อม (E) ที่แตกต่างกัน เช่น สังเกตว่านิยามข้างต้นจะไม่สามารถมีเส้นเชื่อมในกราฟสองเส้นที่เชื่อมจุดยอดสองจุดในลักษณะเดียวกันได้ เนื่องจาก E เป็นเซต ซึ่งสมาชิกที่เหมือนกันจะถูกมองเป็นเพียงแค่หนึ่งตัว หากเปลี่ยน E ให้กลายเป็นก็จะได้สิ่งที่เรียกว่าหรือแทนกราฟปกติ ซึ่งรองรับเส้นเชื่อมหลายๆเส้นที่เชื่อมระหว่างจุดยอดสองจุดที่เหมือนกัน หรือที่เรียกว่า เส้นเชื่อมขนาน (เส้นเชื่อมสีแดงตามภาพด้านขวา)
สำหรับประเภทของกราฟต่างๆที่สมบูรณ์มากกว่านี้ โปรดดูข้างล่าง
จุดยอดที่อยู่ที่ปลายของเส้นเชื่อมจะเรียกว่าจุดยอดปลายของเส้นเชื่อม แต่จุดยอดอาจจะไม่เป็นจุดยอดปลายก็ได้ (ในกรณีที่จุดยอดนั้นไม่มีเส้นเชื่อมมาต่อเลย)
V และ E โดยปกติจะเป็นเซตจำกัด ถึงแม้ว่าจะเป็นไปได้ที่ V หรือ E จะเป็นเซตอนันต์ แต่นิยามหลายๆอย่างจะใช้ไม่ได้ในกรณีนั้น อันดับของกราฟคือ |V| (จำนวนจุดยอด) ส่วนขนาดของกราฟคือ |E| (จำนวนเส้นเชื่อม) ระดับขั้นของจุดยอดคือจำนวนของเส้นเชื่อมที่ต่อกับจุดยอดนั้นๆ ในกรณีที่มีเส้นเชื่อมที่ปลายสองด้านต่อเข้ากับจุดยอดเดียวกัน หรือที่เรียกว่าวงวน (เส้นเชื่อมสีน้ำเงินตามภาพด้านขวา) ให้นับระดับขั้นเพิ่ม 2 สำหรับ 1 วงวน
เส้นเชื่อม {u , v} อาจเขียนให้สั้นว่า uv ก็ได้..
ประเภทของกราฟ
ตามที่ได้กล่าวมาแล้วว่ากราฟมีหลายประเภท อย่างไรก็ตามกราฟในความหมายโดยทั่วไปจะหมายถึงกราฟไม่ระบุทิศทางอย่างง่ายและจำกัด
แบ่งตามทิศทาง
กราฟไม่ระบุทิศทาง
กราฟไม่ระบุทิศทาง (undirected graph) G คือคู่อันดับ G = (V, E) ที่ E คือ เซตของเส้นเชื่อมซึ่งเป็นคู่ไม่อันดับของจุดยอด e = {x, y} จะถูกพิจารณาว่าเป็นเส้นเชื่อม เชื่อมระหว่าง x กับ y โดยที่ทั้ง x และ y จะถูกเรียกว่า จุดยอดปลาย (end vertices) ของเส้นเชื่อม
กราฟระบุทิศทาง
กราฟระบุทิศทาง (directed graph) หรือ ไดกราฟ D คือคู่อันดับ D = (V, A) ที่ A คือ เซตของเส้นเชื่อมระบุทิศทางซึ่งเป็นคู่อันดับของจุดยอด เส้นเชื่อมระบุทิศทาง (directed edges) อาจถูกเรียกว่า อาร์ก (arcs) หรือ ลูกศร (arrows) เส้นเชื่อม e = (x, y) จะถูกพิจารณาว่าเป็นเส้นเชื่อม จาก x ไป y โดยที่ y จะถูกเรียกว่า หัว (head) และ x จะถูกเรียกว่า หาง (tail) ของเส้นเชื่อม เส้นเชื่อม (y, x) จะถูกเรียกว่าเป็นเส้นเชื่อมกลับทิศของ (x, y)
กราฟระบุทิศทาง D จะถูกเรียกว่า สมมาตร ก็ต่อเมื่อทุกๆเส้นเชื่อม (x,y) มีเส้นเชื่อม (y,x) อยู่ในกราฟด้วย ในแง่การไปถึงกันได้ กราฟระบุทิศทางที่สมมาตร D จะเทียบเท่ากับกราฟไม่ระบุทิศทาง G โดยเส้นเชื่อม (x,y) และ (y,x) เทียบเท่ากับเส้นเชื่อม {x,y} ดังนั้น หากเปรียบเทียบระหว่างกราฟระบุทิศทางที่สมมาตรและกราฟไม่ระบุทิศทาง ที่เทียบเท่ากัน จะได้ว่า |E| = |A|/2
(directed acyclic graph: DAG) คือ กราฟระบุทิศทาง ที่ไม่มี
กราฟผสม
กราฟผสม (mixed graph) G คือ (3-tuple) G = (V,E,A) โดยที่ V, E และ A เหมือนดังนิยามด้านบน
แบ่งตามความซับซ้อน
กราฟอย่างง่าย
กราฟอย่างง่าย หรือ กราฟเชิงเดียว (simple graph) เป็นกราฟที่ไม่มี วงวน (loop) ซึ่งเกิดจากเส้นเชื่อมที่มีจุดเริ่มต้นเป็นจุดเดียวกับจุดปลาย และไม่มีเส้นเชื่อมขนาน (parallel edge) ซึ่งเกิดจากเส้นเชื่อมที่มีจุดเริ่มต้นและจุดปลายเหมือนกัน
มัลติกราฟ
มัลติกราฟ (multigraph) เป็นกราฟที่อนุญาตให้มีเส้นเชื่อมขนานได้ โดยเซตของเส้นเชื่อม E หรือ A จะถูกกำหนดเป็นแทน เพื่อให้สามารถใส่เส้นเชื่อมสองเส้นที่เหมือนกันลงในกราฟได้
อย่างไรก็ตาม มัลติกราฟก็ยังถูกนิยามไม่ตรงกัน บ้างก็นิยามว่ามัลติกราฟไม่มีวงวน บ้างก็นิยามว่ากราฟมีวงวนได้ จึงมีการใช้คำว่า (pseudo graph) เพื่อระบุว่ากราฟสามารถมีได้ทั้งเส้นเชื่อมซ้ำและวงวน
แบ่งตามขนาด
กราฟ G = (V,E) จะเป็นกราฟจำกัด (finite graph) ก็ต่อเมื่อ V และ E เป็นเซตจำกัด ในทางตรงกันข้าม หากมี V หรือ E อย่างใดอย่างหนึ่งที่เป็น ก็จะได้ว่า G เป็นกราฟอนันต์ (infinite graph)
แบ่งตามน้ำหนัก
กราฟถ่วงน้ำหนัก (weighted graph) คือ กราฟที่มีการกำหนดค่าให้กับเส้นเชื่อมแต่ละเส้น ซึ่งอาจเป็น ค่าใช้จ่าย, น้ำหนัก, ความยาว หรืออื่นๆขึ้นกับการใช้งาน บางคนเรียกกราฟประเภทนี้ว่าเครือข่าย กราฟถ่วงน้ำหนักนำไปใช้ในการแก้ปัญหาหลายๆอย่าง เช่น ปัญหาวิถีสั้นสุด เป็นต้น โดยทั่วไปน้ำหนักที่ถ่วงจะถือว่าเป็นจำนวนจริงบวก ในกรณีที่น้ำหนักเส้นเชื่อมเป็นลบได้จะมีการระบุเพิ่มเติม เนื่องจากการจัดการกับกรณีทั้งสองในหลายๆปัญหานั้นต่างกัน
โดยทั่วไปหากกล่าวถึงกราฟจะหมายถึงกราฟไม่ถ่วงน้ำหนัก (unweighted graph) ซึ่งไม่มีน้ำหนักถ่วงที่เส้นเชื่อม
คุณลักษณะของกราฟ
เราจะกล่าวว่า
- เส้นเชื่อมสองเส้น ประชิด (adjacent) กัน ถ้าเส้นเชื่อมทั้งสองมีจุดปลายร่วมกัน
- จุดยอดสองจุด ประชิด กัน ถ้าจุดยอดทั้งสองเป็นจุดปลายของเส้นเชื่อมเดียวกัน
- เส้นเชื่อม ต่อ (incident) กับจุดปลายของเส้นเชื่อมเสมอ
กราฟที่มีจุดยอดเพียงจุดเดียวและไม่มีเส้นเชื่อมใดๆ เรียกว่า กราฟชัด (trivial graph) กราฟที่มีแต่จุดยอดแต่ไม่มีเส้นเชื่อมใดๆ เรียกว่า กราฟว่าง (empty graph) ส่วนกราฟที่ไม่มีทั้งจุดยอดและเส้นเชื่อม เรียกว่า กราฟศูนย์ (null graph) แต่นิยามนี้ไม่เป็นที่นิยมนัก
โดยทั่วไปแล้วจุดยอดของกราฟนั้นจะไม่สามารถถูกแยกแยะ หรือพิจารณาว่าแตกต่างกันได้ (ยกเว้นในบางกรณีเช่นมีจำนวนเส้นเชื่อมที่แตกต่างกันเป็นต้น) อย่างไรก็ตาม บางสาขาของทฤษฎีกราฟต้องการให้ระบุจุดยอดที่ชัดเจนได้ ถ้าแต่ละจุดยอดมีการระบุชื่อที่ชัดเจน กล่าวคือมีป้ายชื่อกำกับ เราจะเรียกกราฟเหล่านั้นนั้นว่า กราฟจุดยอดระบุชื่อ (vertex-labeled graph) นอกจากนี้ เส้นเชื่อมก็ยังสามารถมีป้ายชื่อกำกับได้เช่นกัน เรียกกราฟลักษณะนี้ว่า กราฟเส้นเชื่อมระบุชื่อ (edge-labeled graph) ในกรณีที่ไม่มีการระบุชื่อจะเรียกกราฟว่า กราฟไม่ระบุชื่อ (unlabeled graph)
ตัวอย่าง
จากรูปทางขวา เขียนเป็นกราฟได้ดังนี้
- V = {1,2,3,4,5,6}
- E = {{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}
- ใน สามารถพิจารณาเป็นกราฟระบุทิศทาง โดยที่วัตถุที่กล่าวถึงจะเป็นจุดยอด และ (morphism) เป็นเส้นเชื่อมระบุทิศทาง ด้วยการแสดงเช่นนี้ ระหว่างสองประเภทคือ
- ในวิทยาการคอมพิวเตอร์ กราฟระบุทิศทางมักใช้แสดง เครื่องจักรสถานะจำกัด และโครงสร้างอีกหลาย ๆ แบบ
กราฟที่สำคัญ
- กราฟบริบูรณ์ (complete graph) คือ กราฟที่ทุก ๆ คู่ของจุดยอดจะถูกเชื่อมด้วยเส้นเชื่อม ดังนั้น กราฟนี้จะมีเส้นเชื่อมทุกเส้นที่เป็นไปได้
- กราฟเชิงระนาบ (planar graph) คือ กราฟที่สามารถเขียนบนระนาบได้ โดยไม่มีเส้นเชื่อมใดๆตัดกัน
- ต้นไม้ (tree) คือ กราฟเชื่อมโยงที่ไม่มี
- กราฟสองส่วน (bipartite graph)
- (Perfect graph)
- กราฟเส้น (Line graph)
- (Cograph)
- (Directed acyclic graph)
ในทั่วไปของกราฟ
ใน เส้นเชื่อมสามารถเชื่อมได้มากกว่าสองจุด
ทุก ๆ กราฟ ก่อให้เกิด แต่โดยทั่วไปแล้ว เราจะไม่สามารถสร้างกราฟกลับมาจากเมทรอยด์ของมันได้ ดังนั้นเมทรอยด์จึงไม่ใช่นัยทั่วไปของกราฟ
ใน กราฟเป็นแค่โครงสร้าง ในกรณีนั้นจะไม่มีข้อจำกัดในจำนวนของเส้นเชื่อม นั่นคือจะมีเส้นเชื่อมเป็นใด ๆ ก็ได้
อ้างอิง
- Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. ed.). New York: Dover Pub. p. 19. ISBN . สืบค้นเมื่อ 8 August 2012.
A graph is an object consisting of two sets called its vertex set and its edge set.
- Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. . p. 35. ISBN .
- ตัวอย่างเช่น Iyanaga and Kawada, 69 J, หน้า 234 หรือ Biggs, หน้า 4
- ตัวอย่างเช่น Balakrishnan, หน้า 1, Gross (2003), หน้า 4 และ Zwillinger, หน้า 220
- ตัวอย่างเช่น Bollobás, หน้า 7 และ Diestel, หน้า 25.
ดูเพิ่ม
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
lingkkhamphasa inbthkhwamni miiwihphuxanaelaphurwmaekikhbthkhwamsuksaephimetimodysadwk enuxngcakwikiphiediyphasaithyyngimmibthkhwamdngklaw krann khwrribsrangepnbthkhwamodyerwthisud inkhnitsastraelawithyakarkhxmphiwetxr kraf xngkvs Graph prakxbipdwyestkhxngwtthuthieriykwacudyxd vertex sungechuxmtxkndwyesnechuxm edge odythwipaelweramkwadrupaesdngkrafodyichcud aethncudyxd echuxmkndwyesn aethnesnechuxm krafepnwtthuphunthankhxngkarsuksainwiyutkhnit hwkhxthvsdikrafkhxngthimicudyxd 6 cud aelaesnechuxm 7 esn esnechuxmxacmithisthanghruximkid twxyangechn smmutiihcudyxdaethnkhnaelaesnechuxmaethnkarcbmuxkn esnechuxmkcaepnesnechuxmimmithis ephraakarthi A cbmux B kaeplwa B cbmux A xyangirktam smmutithacudyxdaethnkhnaelaesnechuxmaethnkarruck esnechuxmktxngepnesnechuxmmithisthang ephraa A ruck B imcaepnwa B txngruck A hruxnnkkhuxkhwamsmphnthkarruckimepn cudyxdxaccathukeriykwaohnd pm hruxcud inkhnathiesnechuxmxacthukeriykwaesn khawa kraf thukichkhrngaerkody inpi ph s 2421niyamtwxyangthwipkhxngkraf xnthicringkhux sungmi 3 cudyxdaela 6 esnechuxm odythwipkraf G khuxkhuxndb G V E odythi V khuxestkhxngcudyxd aela E khuxestkhxngesnechuxmsungepnkhuimxndbkhxngcudyxd xnthicringniyamthiklawipepnephiyngpraephthhnungkhxngkrafthieriykwa krafimrabuthisthang aelaepn krafxyangngay krafpraephthxuncamiraylaexiydkhxngestesnechuxm E thiaetktangkn echn sngektwaniyamkhangtncaimsamarthmiesnechuxminkrafsxngesnthiechuxmcudyxdsxngcudinlksnaediywknid enuxngcak E epnest sungsmachikthiehmuxnkncathukmxngepnephiyngaekhhnungtw hakepliyn E ihklayepnkcaidsingthieriykwahruxaethnkrafpkti sungrxngrbesnechuxmhlayesnthiechuxmrahwangcudyxdsxngcudthiehmuxnkn hruxthieriykwa esnechuxmkhnan esnechuxmsiaedngtamphaphdankhwa sahrbpraephthkhxngkraftangthismburnmakkwani oprddukhanglang cudyxdthixyuthiplaykhxngesnechuxmcaeriykwacudyxdplaykhxngesnechuxm aetcudyxdxaccaimepncudyxdplaykid inkrnithicudyxdnnimmiesnechuxmmatxely V aela E odypkticaepnestcakd thungaemwacaepnipidthi V hrux E caepnestxnnt aetniyamhlayxyangcaichimidinkrninn xndbkhxngkrafkhux V canwncudyxd swnkhnadkhxngkrafkhux E canwnesnechuxm radbkhnkhxngcudyxdkhuxcanwnkhxngesnechuxmthitxkbcudyxdnn inkrnithimiesnechuxmthiplaysxngdantxekhakbcudyxdediywkn hruxthieriykwawngwn esnechuxmsinaengintamphaphdankhwa ihnbradbkhnephim 2 sahrb 1 wngwn esnechuxm u v xacekhiynihsnwa uv kid praephthkhxngkraftamthiidklawmaaelwwakrafmihlaypraephth xyangirktamkrafinkhwamhmayodythwipcahmaythungkrafimrabuthisthangxyangngayaelacakd aebngtamthisthang krafimrabuthisthang krafimmirabuthisthangxyangngaythimisamcudyxd samesnechuxm aetlacudyxdmiradbkhnepnsxng krafimrabuthisthang undirected graph G khuxkhuxndb G V E thi E khux estkhxngesnechuxmsungepnkhuimxndbkhxngcudyxd e x y cathukphicarnawaepnesnechuxm echuxmrahwang x kb y odythithng x aela y cathukeriykwa cudyxdplay end vertices khxngesnechuxm krafrabuthisthang krafrabuthisthang krafrabuthisthang directed graph hrux idkraf D khuxkhuxndb D V A thi A khux estkhxngesnechuxmrabuthisthangsungepnkhuxndbkhxngcudyxd esnechuxmrabuthisthang directed edges xacthukeriykwa xark arcs hrux luksr arrows esnechuxm e x y cathukphicarnawaepnesnechuxm cak x ip y odythi y cathukeriykwa hw head aela x cathukeriykwa hang tail khxngesnechuxm esnechuxm y x cathukeriykwaepnesnechuxmklbthiskhxng x y krafrabuthisthang D cathukeriykwa smmatr ktxemuxthukesnechuxm x y miesnechuxm y x xyuinkrafdwy inaengkaripthungknid krafrabuthisthangthismmatr D caethiybethakbkrafimrabuthisthang G odyesnechuxm x y aela y x ethiybethakbesnechuxm x y dngnn hakepriybethiybrahwangkrafrabuthisthangthismmatraelakrafimrabuthisthang thiethiybethakn caidwa E A 2 directed acyclic graph DAG khux krafrabuthisthang thiimmi krafphsm krafphsm mixed graph G khux 3 tuple G V E A odythi V E aela A ehmuxndngniyamdanbn aebngtamkhwamsbsxn krafxyangngay krafxyangngay hrux krafechingediyw simple graph epnkrafthiimmi wngwn loop sungekidcakesnechuxmthimicuderimtnepncudediywkbcudplay aelaimmiesnechuxmkhnan parallel edge sungekidcakesnechuxmthimicuderimtnaelacudplayehmuxnkn mltikraf mltikraf multigraph epnkrafthixnuyatihmiesnechuxmkhnanid odyestkhxngesnechuxm E hrux A cathukkahndepnaethn ephuxihsamarthisesnechuxmsxngesnthiehmuxnknlnginkrafid xyangirktam mltikrafkyngthukniyamimtrngkn bangkniyamwamltikrafimmiwngwn bangkniyamwakrafmiwngwnid cungmikarichkhawa pseudo graph ephuxrabuwakrafsamarthmiidthngesnechuxmsaaelawngwn aebngtamkhnad kraf G V E caepnkrafcakd finite graph ktxemux V aela E epnestcakd inthangtrngknkham hakmi V hrux E xyangidxyanghnungthiepn kcaidwa G epnkrafxnnt infinite graph aebngtamnahnk krafthwngnahnk weighted graph khux krafthimikarkahndkhaihkbesnechuxmaetlaesn sungxacepn khaichcay nahnk khwamyaw hruxxunkhunkbkarichngan bangkhneriykkrafpraephthniwaekhruxkhay krafthwngnahnknaipichinkaraekpyhahlayxyang echn pyhawithisnsud epntn odythwipnahnkthithwngcathuxwaepncanwncringbwk inkrnithinahnkesnechuxmepnlbidcamikarrabuephimetim enuxngcakkarcdkarkbkrnithngsxnginhlaypyhanntangkn odythwiphakklawthungkrafcahmaythungkrafimthwngnahnk unweighted graph sungimminahnkthwngthiesnechuxmkhunlksnakhxngkraferacaklawwa esnechuxmsxngesn prachid adjacent kn thaesnechuxmthngsxngmicudplayrwmkn cudyxdsxngcud prachid kn thacudyxdthngsxngepncudplaykhxngesnechuxmediywkn esnechuxm tx incident kbcudplaykhxngesnechuxmesmx krafthimicudyxdephiyngcudediywaelaimmiesnechuxmid eriykwa krafchd trivial graph krafthimiaetcudyxdaetimmiesnechuxmid eriykwa krafwang empty graph swnkrafthiimmithngcudyxdaelaesnechuxm eriykwa krafsuny null graph aetniyamniimepnthiniymnk odythwipaelwcudyxdkhxngkrafnncaimsamarththukaeykaeya hruxphicarnawaaetktangknid ykewninbangkrniechnmicanwnesnechuxmthiaetktangknepntn xyangirktam bangsakhakhxngthvsdikraftxngkarihrabucudyxdthichdecnid thaaetlacudyxdmikarrabuchuxthichdecn klawkhuxmipaychuxkakb eracaeriykkrafehlannnnwa krafcudyxdrabuchux vertex labeled graph nxkcakni esnechuxmkyngsamarthmipaychuxkakbidechnkn eriykkraflksnaniwa krafesnechuxmrabuchux edge labeled graph inkrnithiimmikarrabuchuxcaeriykkrafwa krafimrabuchux unlabeled graph twxyangkrafthimicudyxd 6 cud aelaesnechuxm 7 esn cakrupthangkhwa ekhiynepnkrafiddngni V 1 2 3 4 5 6 E 1 2 1 5 2 3 2 5 3 4 4 5 4 6 in samarthphicarnaepnkrafrabuthisthang odythiwtthuthiklawthungcaepncudyxd aela morphism epnesnechuxmrabuthisthang dwykaraesdngechnni rahwangsxngpraephthkhux inwithyakarkhxmphiwetxr krafrabuthisthangmkichaesdng ekhruxngckrsthanacakd aelaokhrngsrangxikhlay aebbkrafthisakhykrafbriburn complete graph khux krafthithuk khukhxngcudyxdcathukechuxmdwyesnechuxm dngnn krafnicamiesnechuxmthukesnthiepnipid krafechingranab planar graph khux krafthisamarthekhiynbnranabid odyimmiesnechuxmidtdkn tnim tree khux krafechuxmoyngthiimmi krafsxngswn bipartite graph Perfect graph krafesn Line graph Cograph Directed acyclic graph inthwipkhxngkrafin esnechuxmsamarthechuxmidmakkwasxngcud thuk kraf kxihekid aetodythwipaelw eracaimsamarthsrangkrafklbmacakemthrxydkhxngmnid dngnnemthrxydcungimichnythwipkhxngkraf in krafepnaekhokhrngsrang inkrninncaimmikhxcakdincanwnkhxngesnechuxm nnkhuxcamiesnechuxmepnid kidxangxingTrudeau Richard J 1993 Introduction to Graph Theory Corrected enlarged republication ed New York Dover Pub p 19 ISBN 978 0 486 67870 2 subkhnemux 8 August 2012 A graph is an object consisting of two sets called its vertex set and its edge set Gross Jonathan L Yellen Jay 2004 Handbook of graph theory p 35 ISBN 978 1 58488 090 5 twxyangechn Iyanaga and Kawada 69 J hna 234 hrux Biggs hna 4 twxyangechn Balakrishnan hna 1 Gross 2003 hna 4 aela Zwillinger hna 220 twxyangechn Bollobas hna 7 aela Diestel hna 25 duephimxphithansphththvsdikraf