ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
ทฤษฎีกราฟเติบโตอย่างรวดเร็วในวงการวิจัยด้านคณิตศาสตร์ และมีคำศัพท์เฉพาะทางอยู่หลายคำ บทความนี้จะรวบรวมคำและความหมายของศัพท์ในทฤษฎีกราฟ
พื้นฐาน
กราฟ G มีส่วนประกอบพื้นฐานอยู่ 2 ส่วนคือ จุดยอด และ เส้นเชื่อม เส้นเชื่อมทุกเส้นมีจุดยอดปลาย 2 จุด ซึ่งจุดยอดปลายจะเชื่อมโยงหรือประชิดกัน ดังนั้นจึงสามารถนิยามเส้นเชื่อมในรูปแบบของคู่ไม่อันดับในกรณีของกราฟไม่มีทิศทาง หรือคู่อันดับในกรณีของกราฟมีทิศทาง (อ่านหัวข้อทิศทาง)
จุดยอด มักเขียนแทนด้วยจุด เซตจุดยอดของ G เขียนแทนด้วย V(G) หรือ V อันดับของกราฟ คือ จำนวนของจุดยอด ซึ่งเท่ากับ |V(G)|
เส้นเชื่อม (ในที่นี้คือเส้นเชื่อมไม่มีทิศทางซึ่งเป็นคู่ไม่อันดับของจุดยอด) มักเขียนแทนด้วยเส้นที่เชื่อมระหว่างจุดยอด (จุดยอดปลาย) 2 จุด เส้นเชื่อมที่มีจุดยอดปลายเป็น x กับ y จะเขียนแทนด้วย xy โดยไม่มีสัญลักษณ์ใดๆอยู่ตรงกลาง เซตของเส้นเชื่อมของ G เขียนแทนด้วย E (G) หรือ E
ขนาดของกราฟ คือจำนวนของเส้นเชื่อม ซึ่งเท่ากับ |E(G)|
คือ เส้นเชื่อมที่มีจุดยอดปลายเป็นจุดยอดเดียวกัน ลิงก์ คือ เส้นเชื่อมที่มีจุดยอดปลายทั้ง 2 เป็นคนละจุด เส้นเชื่อมซ้ำ คือ เส้นเชื่อมที่มีเส้นเชื่อมอื่นเชื่อมจุดยอดปลายทั้งสองของมันเหมือนกัน เส้นเชื่อมเชิงเดียว คือ เส้นเชื่อมที่ไม่เป็นเส้นเชื่อมซ้ำ กราฟเชิงเดียว คือ กราฟที่ไม่มีเส้นเชื่อมซ้ำและไม่มีวงวน คือ กราฟที่อาจมีเส้นเชื่อมซ้ำแต่นิยามอนุญาตให้มีวงวนหรือไม่มีวงวนก็ได้ คือกราฟที่อาจมีเส้นเชื่อมซ้ำและอาจมีวงวน
การระบุชื่อกราฟ คือ การกำหนดชื่อให้กับเส้นเชื่อมและจุดยอดของกราฟ (โดยทั่วไปมักกำหนดชื่อด้วยจำนวนธรรมชาติ) กราฟที่ระบุชื่อให้กับเส้นเชื่อมหรือจุดยอด จะเรียกว่า ถ้าไม่ได้ระบุชื่อ เรียกว่า กราฟไม่ระบุชื่อ อาจจำแนกเป็นการระบุชื่อที่จุดยอดหรือเส้นเชื่อมอีกก็ได้
กราฟศูนย์ คือ กราฟที่ไม่มีจุดยอดและไม่มีเส้นเชื่อมอยู่เลย หรือ เป็นกราฟที่ไม่มีเส้นเชื่อม แต่มีจุดยอดอยู่จำนวนหนึ่ง ในกรณีนี้เราจะเรียกว่า กราฟศูนย์บนจุดยอด n จุด
กราฟอนันต์ คือ กราฟที่มีจุดยอดอยู่เป็นอนันต์ หรือมีเส้นเชื่อมอยู่เป็นอนันต์ กราฟที่ไม่เป็นกราฟอนันต์ เรียกว่า กราฟจำกัด
กราฟ G และ H จะสมสัณฐาน ก็ต่อเมื่อ เราสามารถจับคู่หนึ่งต่อหนึ่งระหว่างจุดยอดของกราฟทั้งสองได้ โดยที่ จุดยอดสองจุดใดๆใน G จะประชิดกันก็ต่อเมื่อ จุดยอดสองจุดที่สมนัยกับมันใน H ประชิดกันด้วย
กราฟย่อย
กราฟย่อย ของกราฟ G คือกราฟที่มีเซตจุดยอดและเซตเส้นเชื่อม เป็นเซตย่อยของ G
แนวเดิน
แนวเดิน คือ ลำดับสลับระหว่างจุดยอดและเส้นเชื่อม โดยเริ่มต้นและลงท้ายที่จุดยอด โดยที่จุดยอดจะต่อกับเส้นเชื่อมที่อยู่หน้าและตามหลังมันในลำดับ แนวเดินปิดคือแนวเดินที่จุดยอดแรกและจุดยอดท้ายเป็นจุดยอดเดียวกัน แนวเดินที่ไม่เป็นแนวเดินปิดเรียกว่า แนวเดินเปิด
ความยาวของแนวเดิน คือ จำนวนเส้นเชื่อมที่ใช้ในแนวเดิน
รอยเดิน คือ แนวเดินที่ใช้เส้นเชื่อมแต่ละเส้นเพียงครั้งเดียว รอยเดินปิด เรียกว่า ทัวร์ หรือ วงจร
วิถี มักหมายถึง แนวเดินเปิด โดยทั่วไปแล้ว วิถีมักจะหมายถึงวิถีเชิงเดียว นั่นคือ จุดยอดทุกจุดจะติดกับเส้นเชื่อมอย่างมากสองเส้น จากกราฟตัวอย่างข้างบน (5, 2, 1) คือ วิถีที่มีความยาวเท่ากับ 2 วัฏจักร คือ วิถีที่จุดเริ่มต้นกับจุดท้ายเป็นจุดเดียวกัน จากกราฟตัวอย่าง (1, 5, 2, 1) เป็นวัฏจักรที่มีความยาวเท่ากับ 3 วิถีที่มีจุดยอด n จุด เขียนแทนด้วย Pn วัฏจักรที่มีจุดยอด n จุด เขียนแทนด้วย Cn (อย่างไรก็ตาม มีผู้เขียนบางคนใช้ความยาวแทนจำนวนจุดยอด)
วัฏจักรคี่ คือ วัฏจักรที่มีความยาวเป็นจำนวนคี่ วัฏจักรคู่ คือ วัฏจักรที่มีความยาวเป็นจำนวนคู่ มีทฤษฎีบทหนึ่งกล่าวว่า กราฟจะเป็นกราฟสองส่วน ก็ต่อเมื่อ มันไม่มีวัฏจักรคี่อยู่
ของกราฟ คือ ความยาวของวัฏจักร (เชิงเดียว) ที่สั้นที่สุดในกราฟ เส้นรอบวงของกราฟ คือ ความยาวของวัฏจักร (เชิงเดียว) ที่ยาวที่สุดในกราฟ กราฟที่ไม่มีวัฏจักรจะถือว่ามี girth และเส้นรอบวง เท่ากับอนันต์ ∞
กราฟอวัฏจักร คือ กราฟที่ไม่มีวัฏจักร คือกราฟที่มีวัฏจักรอยู่ 1 วัฏจักร
C1 เรียกว่า วงวน C2 เรียกว่าคู่ของเส้นเชื่อมซ้ำ C3 เรียกว่า รูปสามเหลี่ยม
ต้นไม้
ต้นไม้ คือ กราฟเชิงเดียวเชื่อมโยงที่ไม่มีวัฏจักร ใบ คือ จุดยอดที่มีระดับขั้นเท่ากับ 1 เส้นเชื่อมใบ คือ เส้นเชื่อมที่ต่อกับใบ จุดยอดที่ไม่ใช่ใบเรียกว่า จุดยอดภายใน ต้นไม้จะถูกเรียกว่า ต้นไม้มีราก ถ้ามีจุดยอดหนึ่งจุดที่ถูกกำหนดให้เป็นราก ต้นไม้มีรากจะเป็นเมื่อเส้นเชื่อมชี้ออกจากรากเสมอ
ต้นไม้ เป็นโครงสร้างข้อมูลที่นิยมใช้กันในวิทยาการคอมพิวเตอร์ (ดูโครงสร้างข้อมูลแบบต้นไม้)
ป่า คือ กลุ่มของต้นไม้ที่ไม่มีจุดยอดร่วมกัน
ต้นไม้ย่อยของกราฟ G คือ กราฟย่อยที่เป็นต้นไม้
ต้นไม้ทอดข้าม คือ กราฟย่อยทอดข้ามที่เป็นต้นไม้ กราฟเชื่อมโยงจะมีต้นไม้ทอดข้ามเสมอ
กลุ่มพรรคพวก
กราฟแบบบริบูรณ์ Kn คือ กราฟเชิงเดียวที่มีจุดยอด n จุด และจุดยอดทุกจุดจะประชิดกับจุดยอดอื่นๆทุกจุด กราฟแบบบริบูรณ์ที่มีจุดยอด n จุด เขียนแทนด้วย Kn ซึ่งจะมีเส้นเชื่อม n (n-1)/2 เส้น
ในกราฟ คือ กลุ่มของจุดยอดที่จุดยอดทุกจุดในกลุ่มประชิดกัน กลุ่มพรรคพวกอันดับ k คือ กลุ่มพรรคพวกที่มีจุดยอด k จุด จากตัวอย่างข้างบน จุดยอด 1, 2, 5 เป็นกลุ่มพรรคพวกอันดับ 3 หรือเรียกว่า รูปสามเหลี่ยม
หมายเลขกลุ่มพรรคพวก ω (G) ของกราฟ G คือ อันดับของกลุ่มพรรคพวกที่ใหญ่สุดใน G
ส่วนประกอบที่เชื่อมกันแบบเข้ม
การประชิด และระดับขั้น
ระดับขั้น dG (v) ของจุดยอด v ในกราฟ G คือ จำนวนเส้นเชื่อมที่ต่อกับ v ถ้าเส้นเชื่อมเป็นวงวนให้นับสองครั้ง จุดเอกเทศ คือ จุดยอดที่มีระดับขั้น 0. ใบ คือ จุดยอดที่มีระดับขั้น 1. จากกราฟตัวอย่าง จุดยอด 1 และ 3 มีระดับขั้น 2. จุดยอด 2, 4, 5 มีระดับขั้น 3. จุดยอด 6 มีระดับขั้น 1. ถ้า E เป็นเซตจำกัดแล้ว ผลบวกของระดับขั้นของจุดยอดในกราฟ จะเท่ากับจำนวนเส้นเชื่อมคูณสอง
ลำดับระดับขั้น คือรายการของระดับขั้นของกราฟ ที่เรียงลำดับจากมากไปน้อย (d1 ≥ d2 ≥ … ≥ dn)
จุดยอด u และจุดยอด v จะประชิดกัน ถ้ามีเส้นเชื่อมเชื่อมระหว่าง u กับ v เขียนแทนด้วย u ↓ v จากกราฟตัวอย่าง จุดยอด 1 กับ 2 ประชิดกัน แต่จุดยอด 2 กับ 4 ไม่ประชิดกัน
ระดับขั้นสูงสุด Δ (G) ของกราฟ G คือระดับขั้นที่มีค่าสูงสุดของจุดยอดในกราฟ ระดับขั้นต่ำสุด δ (G) ของกราฟ G คือระดับขั้นที่มีค่าต่ำสุดของจุดยอดในกราฟ
ความต่อเนื่อง
ระยะทาง
ส่วนนี้รอเพิ่มเติมข้อมูล คุณสามารถช่วยเพิ่มข้อมูลส่วนนี้ได้ |
กราฟถ่วงน้ำหนักและเครือข่าย
กราฟถ่วงน้ำหนัก (weighted graph) คือ กราฟที่มีการกำหนดค่าให้กับเส้นเชื่อมแต่ละเส้น ซึ่งอาจเป็น ค่าใช้จ่าย, น้ำหนัก, ความยาว หรืออื่นๆขึ้นกับการใช้งาน บางคนเรียกกราฟประเภทนี้ว่าเครือข่าย กราฟถ่วงน้ำหนักนำไปใช้ในการแก้ปัญหาหลายๆอย่าง เช่น ปัญหาวิถีสั้นสุด เป็นต้น โดยทั่วไปน้ำหนักที่ถ่วงจะถือว่าเป็นจำนวนจริงบวก ในกรณีที่น้ำหนักเส้นเชื่อมเป็นลบได้จะมีการระบุเพิ่มเติม เนื่องจากการจัดการกับกรณีทั้งสองในหลายๆปัญหานั้นต่างกัน
โดยทั่วไปหากกล่าวถึงกราฟจะหมายถึงกราฟไม่ถ่วงน้ำหนัก (unweighted graph) ซึ่งไม่มีน้ำหนักถ่วงที่เส้นเชื่อม
ทิศทาง
กราฟอวัฏจักรระบุทิศทาง
การให้สีกราฟ
อื่นๆ
- (en:hypergraph)
- กราฟสองส่วน
- กราฟสองส่วนบริบูรณ์
- (en:Eulerian path)
- (en:Hamiltonian path)
- เซตอิสระ
- (en:Matching (graph theory))
- (en:Bridge (graph theory))
- (en:Distance (graph theory))
- กราฟเชิงระนาบ
- ปัญหาวิถีสั้นสุด
- ต้นไม้ทอดข้ามที่น้อยที่สุด
- (en:Maximum flow)
- (en:graph invariant)
ดูเพิ่ม
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 thvsdikrafetibotxyangrwderwinwngkarwicydankhnitsastr aelamikhasphthechphaathangxyuhlaykha bthkhwamnicarwbrwmkhaaelakhwamhmaykhxngsphthinthvsdikrafphunthankraf G miswnprakxbphunthanxyu 2 swnkhux cudyxd aela esnechuxm esnechuxmthukesnmicudyxdplay 2 cud sungcudyxdplaycaechuxmoynghruxprachidkn dngnncungsamarthniyamesnechuxminrupaebbkhxngkhuimxndbinkrnikhxngkrafimmithisthang hruxkhuxndbinkrnikhxngkrafmithisthang xanhwkhxthisthang cudyxd mkekhiynaethndwycud estcudyxdkhxng G ekhiynaethndwy V G hrux V xndbkhxngkraf khux canwnkhxngcudyxd sungethakb V G esnechuxm inthinikhuxesnechuxmimmithisthangsungepnkhuimxndbkhxngcudyxd mkekhiynaethndwyesnthiechuxmrahwangcudyxd cudyxdplay 2 cud esnechuxmthimicudyxdplayepn x kb y caekhiynaethndwy xy odyimmisylksnidxyutrngklang estkhxngesnechuxmkhxng G ekhiynaethndwy E G hrux E khnadkhxngkraf khuxcanwnkhxngesnechuxm sungethakb E G khux esnechuxmthimicudyxdplayepncudyxdediywkn lingk khux esnechuxmthimicudyxdplaythng 2 epnkhnlacud esnechuxmsa khux esnechuxmthimiesnechuxmxunechuxmcudyxdplaythngsxngkhxngmnehmuxnkn esnechuxmechingediyw khux esnechuxmthiimepnesnechuxmsa krafechingediyw khux krafthiimmiesnechuxmsaaelaimmiwngwn khux krafthixacmiesnechuxmsaaetniyamxnuyatihmiwngwnhruximmiwngwnkid khuxkrafthixacmiesnechuxmsaaelaxacmiwngwn karrabuchuxkraf khux karkahndchuxihkbesnechuxmaelacudyxdkhxngkraf odythwipmkkahndchuxdwycanwnthrrmchati krafthirabuchuxihkbesnechuxmhruxcudyxd caeriykwa thaimidrabuchux eriykwa krafimrabuchux xaccaaenkepnkarrabuchuxthicudyxdhruxesnechuxmxikkid krafechingediywrabuchux thimiestcudyxd V 1 2 3 4 5 6 aelaestesnechuxm E 1 2 1 5 2 3 2 5 3 4 4 5 4 6 krafsuny khux krafthiimmicudyxdaelaimmiesnechuxmxyuely hrux epnkrafthiimmiesnechuxm aetmicudyxdxyucanwnhnung inkrninieracaeriykwa krafsunybncudyxd n cud krafxnnt khux krafthimicudyxdxyuepnxnnt hruxmiesnechuxmxyuepnxnnt krafthiimepnkrafxnnt eriykwa krafcakd kraf G aela H casmsnthan ktxemux erasamarthcbkhuhnungtxhnungrahwangcudyxdkhxngkrafthngsxngid odythi cudyxdsxngcudidin G caprachidknktxemux cudyxdsxngcudthismnykbmnin H prachidkndwy krafyxy krafyxy khxngkraf G khuxkrafthimiestcudyxdaelaestesnechuxm epnestyxykhxng G aenwedin aenwedin khux ladbslbrahwangcudyxdaelaesnechuxm odyerimtnaelalngthaythicudyxd odythicudyxdcatxkbesnechuxmthixyuhnaaelatamhlngmninladb aenwedinpidkhuxaenwedinthicudyxdaerkaelacudyxdthayepncudyxdediywkn aenwedinthiimepnaenwedinpideriykwa aenwedinepid khwamyawkhxngaenwedin khux canwnesnechuxmthiichinaenwedin rxyedin khux aenwedinthiichesnechuxmaetlaesnephiyngkhrngediyw rxyedinpid eriykwa thwr hrux wngcr withi mkhmaythung aenwedinepid odythwipaelw withimkcahmaythungwithiechingediyw nnkhux cudyxdthukcudcatidkbesnechuxmxyangmaksxngesn cakkraftwxyangkhangbn 5 2 1 khux withithimikhwamyawethakb 2 wtckr khux withithicuderimtnkbcudthayepncudediywkn cakkraftwxyang 1 5 2 1 epnwtckrthimikhwamyawethakb 3 withithimicudyxd n cud ekhiynaethndwy Pn wtckrthimicudyxd n cud ekhiynaethndwy Cn xyangirktam miphuekhiynbangkhnichkhwamyawaethncanwncudyxd wtckrkhi khux wtckrthimikhwamyawepncanwnkhi wtckrkhu khux wtckrthimikhwamyawepncanwnkhu mithvsdibthhnungklawwa krafcaepnkrafsxngswn ktxemux mnimmiwtckrkhixyu khxngkraf khux khwamyawkhxngwtckr echingediyw thisnthisudinkraf esnrxbwngkhxngkraf khux khwamyawkhxngwtckr echingediyw thiyawthisudinkraf krafthiimmiwtckrcathuxwami girth aelaesnrxbwng ethakbxnnt krafxwtckr khux krafthiimmiwtckr khuxkrafthimiwtckrxyu 1 wtckr C1 eriykwa wngwn C2 eriykwakhukhxngesnechuxmsa C3 eriykwa rupsamehliym tnim tnim khux krafechingediywechuxmoyngthiimmiwtckr ib khux cudyxdthimiradbkhnethakb 1 esnechuxmib khux esnechuxmthitxkbib cudyxdthiimichiberiykwa cudyxdphayin tnimcathukeriykwa tnimmirak thamicudyxdhnungcudthithukkahndihepnrak tnimmirakcaepnemuxesnechuxmchixxkcakrakesmx tnim epnokhrngsrangkhxmulthiniymichkninwithyakarkhxmphiwetxr duokhrngsrangkhxmulaebbtnim pa khux klumkhxngtnimthiimmicudyxdrwmkn tnimyxykhxngkraf G khux krafyxythiepntnim tnimthxdkham khux krafyxythxdkhamthiepntnim krafechuxmoyngcamitnimthxdkhamesmx klumphrrkhphwk krafaebbbriburn Kn khux krafechingediywthimicudyxd n cud aelacudyxdthukcudcaprachidkbcudyxdxunthukcud krafaebbbriburnthimicudyxd n cud ekhiynaethndwy Kn sungcamiesnechuxm n n 1 2 esn inkraf khux klumkhxngcudyxdthicudyxdthukcudinklumprachidkn klumphrrkhphwkxndb k khux klumphrrkhphwkthimicudyxd k cud caktwxyangkhangbn cudyxd 1 2 5 epnklumphrrkhphwkxndb 3 hruxeriykwa rupsamehliym hmayelkhklumphrrkhphwk w G khxngkraf G khux xndbkhxngklumphrrkhphwkthiihysudin G swnprakxbthiechuxmknaebbekhmkarprachid aelaradbkhnradbkhn dG v khxngcudyxd v inkraf G khux canwnesnechuxmthitxkb v thaesnechuxmepnwngwnihnbsxngkhrng cudexkeths khux cudyxdthimiradbkhn 0 ib khux cudyxdthimiradbkhn 1 cakkraftwxyang cudyxd 1 aela 3 miradbkhn 2 cudyxd 2 4 5 miradbkhn 3 cudyxd 6 miradbkhn 1 tha E epnestcakdaelw phlbwkkhxngradbkhnkhxngcudyxdinkraf caethakbcanwnesnechuxmkhunsxng ladbradbkhn khuxraykarkhxngradbkhnkhxngkraf thieriyngladbcakmakipnxy d1 d2 dn cudyxd u aelacudyxd v caprachidkn thamiesnechuxmechuxmrahwang u kb v ekhiynaethndwy u v cakkraftwxyang cudyxd 1 kb 2 prachidkn aetcudyxd 2 kb 4 imprachidkn radbkhnsungsud D G khxngkraf G khuxradbkhnthimikhasungsudkhxngcudyxdinkraf radbkhntasud d G khxngkraf G khuxradbkhnthimikhatasudkhxngcudyxdinkrafkhwamtxenuxngrayathangswnnirxephimetimkhxmul khunsamarthchwyephimkhxmulswnniidkrafthwngnahnkaelaekhruxkhaykrafthwngnahnk weighted graph khux krafthimikarkahndkhaihkbesnechuxmaetlaesn sungxacepn khaichcay nahnk khwamyaw hruxxunkhunkbkarichngan bangkhneriykkrafpraephthniwaekhruxkhay krafthwngnahnknaipichinkaraekpyhahlayxyang echn pyhawithisnsud epntn odythwipnahnkthithwngcathuxwaepncanwncringbwk inkrnithinahnkesnechuxmepnlbidcamikarrabuephimetim enuxngcakkarcdkarkbkrnithngsxnginhlaypyhanntangkn odythwiphakklawthungkrafcahmaythungkrafimthwngnahnk unweighted graph sungimminahnkthwngthiesnechuxmthisthangkrafxwtckrrabuthisthangkarihsikrafxun en hypergraph krafsxngswn krafsxngswnbriburn en Eulerian path en Hamiltonian path estxisra en Matching graph theory en Bridge graph theory en Distance graph theory krafechingranab pyhawithisnsud tnimthxdkhamthinxythisud en Maximum flow en graph invariant duephimkraf khnitsastr thvsdikrafbthkhwamkhnitsastrniyngepnokhrng khunsamarthchwywikiphiediyidodykarephimetimkhxmuldk