នៅក្នុងមេរៀនទីមួយ ការណែនាំអំពីគំនិតនៃក្រាហ្វមួយ យើងបានចាត់ទុកជាឧទាហរណ៍នៃការប្រកួតប្រជែងរបស់ក្រុមកីឡា។ យើង។ បានភ្ជាប់ក្រុមពីរ និយាយថា A និង C ជាមួយគែម AC ក្នុងករណីនៅពេលដែលក្រុមទាំងនេះកំពុងលេងគ្នាទៅវិញទៅមក។ ទោះជាយ៉ាងណាក៏ដោយក្រាហ្វបែបនេះមិនឆ្លើយសំណួរសំខាន់មួយទេ: តើនរណាជាអ្នកឈ្នះការប្រកួតនេះ?
ចំណុចខ្វះខាតនេះអាចត្រូវបានលុបចោលយ៉ាងងាយស្រួល។ ប្រសិនបើក្រុម A បានឈ្នះទល់នឹង C យើងនឹងយល់ព្រមដាក់ព្រួញនៅលើគែម AC ដែលដឹកនាំពី A ដល់ C ។ ឧបមាថាយើងដឹងពីលទ្ធផលនៃហ្គេមទាំងអស់ដែលបានលេងរួចហើយ ហើយបន្ថែមលើក្រាហ្វិក។ 1 ព្រួញដែលត្រូវគ្នា; សូមឱ្យលទ្ធផលនេះនៅក្នុងក្រាហ្វដែលបង្ហាញក្នុងរូបភព។ ៥៨.

រូបភាព 58 ។

ក្រាហ្វនេះបង្ហាញថាក្រុម A ឈ្នះ C ក្រុម F ចាញ់ក្រុម A ហើយក្រុម B បានឈ្នះការប្រកួតទាំងអស់ជាមួយក្រុម C, E, F ។ល។

គែមក្រាហ្វត្រូវបានគេហៅថា តម្រង់ទិសប្រសិនបើចំនុចមួយត្រូវបានពិចារណា ការចាប់ផ្តើមនៃឆ្អឹងជំនី, និងផ្សេងទៀត - ចប់.
ក្រាហ្វដែលគែមទាំងអស់ត្រូវបានតម្រង់ទិសត្រូវបានគេហៅថា ការតំរង់ទិសរាប់.
ចំនុចកំពូលដូចគ្នានៃក្រាហ្វដែលដឹកនាំអាចដើរតួជាការចាប់ផ្តើមសម្រាប់គែមមួយចំនួន និងចុងបញ្ចប់សម្រាប់ផ្នែកផ្សេងទៀត។ ដូច្នោះហើយពីរដឺក្រេនៃកំពូលត្រូវបានសម្គាល់: សញ្ញាប័ត្រចេញ និងសញ្ញាប័ត្រចូល។
ចេញសញ្ញាបត្រចំនុចកំពូល A នៃក្រាហ្វដែលដឹកនាំគឺជាចំនួនគែមដែលបន្សល់ទុក A (ចំណាំ: d + (A)) ។
កម្រិតនៃការបញ្ចូលចំនុចកំពូល A នៃក្រាហ្វដែលដឹកនាំគឺជាចំនួនធាតុចូល ប៉ុន្តែគែម (និមិត្តសញ្ញា៖ ឃ-(A)) ។
ចុះ​បើ​ការ​ប្រកួត​បញ្ចប់​ដោយ​ស្មើ? យើងអាចឆ្លុះបញ្ចាំងពីលទ្ធផលស្មើនៅលើក្រាហ្វដោយទុកគែមដែលត្រូវគ្នាដោយមិនដឹកនាំ។ ក្នុងការធ្វើដូច្នេះយើងទទួលបានអ្វីដែលគេហៅថា smរាប់ shanyដែល​មាន​ទាំង​គែម​តម្រង់​និង​មិន​តម្រង់។
ផ្លូវនៅក្នុងក្រាហ្វដែលដឹកនាំ G ពី A1 ទៅ An គឺជាលំដាប់នៃគែមតម្រង់ទិស<А1; А2>, <А2; А3>, ..., <Аn-1; Аn>ដូចជាចុងបញ្ចប់នៃគែមមុននីមួយៗស្របគ្នានឹងការចាប់ផ្តើមនៃគែមបន្ទាប់ ហើយគ្មានគែមណាមួយកើតឡើងច្រើនជាងម្តង។

អង្ករ។ ៥៩
ប្រសិនបើនៅក្នុងក្រាហ្វដែលដឹកនាំ G មានផ្លូវពី ប៉ុន្តែទៅ B បន្ទាប់មកត្រឡប់ពី អេទៅ ប៉ុន្តែប្រហែលជាមិនមែនជា (រូបភាព 59) ។
ប្រសិនបើមានផ្លូវដឹកនាំពី A ទៅ B នោះ B ត្រូវបានគេនិយាយថាជា ឈានដល់ម៉ាពី A
នៅក្នុងជួរឈរ G ក្នុងរូបភាព 38 B គឺអាចសម្រេចបាន។
ពី A, A មិនអាចទៅដល់ពី B បានទេ។
វិធីងាយស្រួលក្រាហ្វដឹកនាំគឺជាផ្លូវដែលមិនមានចំនុចកំពូលលើសពីម្តង។ ផ្លូវបិទនៅក្នុងក្រាហ្វដឹកនាំត្រូវបានគេហៅថា វដ្តដឹកនាំ។
ផ្លូវ​ឆ្ងាយគឺជាចំនួនគែមនៅក្នុងផ្លូវនេះ។
ចម្ងាយពី A ទៅ B ក្នុងក្រាហ្វដែលដឹកនាំគឺជាប្រវែងនៃផ្លូវខ្លីបំផុតពី A ទៅ B ។ ប្រសិនបើគ្មានផ្លូវពី A ទៅ B នោះចម្ងាយពី A ទៅ B ត្រូវបានគេហៅថាគ្មានកំណត់ ហើយមានន័យដូចម្តេច? ចម្ងាយពី A ដល់ B នឹងត្រូវបានបង្ហាញដោយ S (AB) ។ សម្រាប់ក្រាហ្វក្នុងរូបភាព 38
S (AB) \u003d 1, S (CB) - 2, S (BC) \u003d ?.
បញ្ហា 9.1 ។
នៅក្នុងទីក្រុងរមណីយដ្ឋានមាត់សមុទ្រ បន្ទាប់ពីការបង្កើតចរាចរណ៍ផ្លូវមួយ វាបានប្រែក្លាយថាចំនួនផ្លូវដែលអ្នកអាចចូលផ្លូវប្រសព្វនីមួយៗគឺស្មើនឹងចំនួនផ្លូវដែលអ្នកអាចទុកវាបាន។ បញ្ជាក់​ថា​អាច​ស្នើ​ផ្លូវ​ល្បាត​ដែល​ចាប់ផ្តើម​និង​បញ្ចប់​នៅ​កន្លែង​ដដែល ហើយ​ឆ្លងកាត់​ផ្នែក​ផ្លូវ​នីមួយៗ​តែម្តង​។
ដំណោះស្រាយ។
អនុញ្ញាតឱ្យយើងបង្កើតតួលេខ G ដែលកំណត់ចលនានៅក្នុងទីក្រុង។
តួលេខត្រូវបានគេហៅថា តភ្ជាប់,ប្រសិនបើ​អាច​ទៅ​ពី​ចំណុច​កំពូល​ណាមួយ​ទៅ​អ័ក្ស​ផ្សេងទៀត​ដោយ​មិន​គិត​ពី​ការ​តំរង់​ទិស​របស់​វា។ លេខដែលភ្ជាប់ត្រូវបានគេហៅថា អយល័រប្រសិនបើវាមានវដ្តអយល័រ។
ទ្រឹស្តីបទ 12. តួរលេខដែលតភ្ជាប់គឺ អយល័រ ប្រសិនបើ និងសម្រាប់តែចំនុចកំពូលនីមួយៗរបស់វា។vសមភាពឃ- (v) = ឃ+ (v) .
ទ្រឹស្តីបទត្រូវបានបញ្ជាក់តាមរបៀបដូចគ្នាទៅនឹងទ្រឹស្តីបទនៅក្នុងបញ្ហា 4.2 ។
វាធ្វើតាមលក្ខខណ្ឌនៃបញ្ហាដែលសម្រាប់ចំនុចកំពូលនៃក្រាហ្វដែលបានសាងសង់ G សមភាព d-(v) = d+(v) ត្រូវបានពេញចិត្ត។ ដូច្នេះ ក្រាហ្វអយល័រ G និងវដ្តអយល័រនឹងកំណត់ផ្លូវល្បាតដែលចង់បាន។
បញ្ហា 9.2 ។
ចំនួនពិន្ទុកំណត់ត្រូវបានសម្គាល់នៅលើយន្តហោះ។ គូនៃចំណុចមួយចំនួនគឺជាការចាប់ផ្តើម និងចុងបញ្ចប់នៃវ៉ិចទ័រ ហើយចំនួនវ៉ិចទ័រដែលចូលចំណុចណាមួយគឺស្មើនឹងចំនួនវ៉ិចទ័រដែលទុកវា។ រកផលបូកនៃវ៉ិចទ័រ។
ដំណោះស្រាយ។
ចំនុចនៃយន្តហោះរួមជាមួយនឹងវ៉ិចទ័របង្កើតជាដ្យាក្រាម G. វដ្ដនៃឌីក្រាហ្វ ចំនុចកំពូលទាំងអស់ដែលខុសគ្នាត្រូវបានគេហៅថា វណ្ឌវង្ក។
ទ្រឹស្តីបទ 13. ដ្យាក្រាមតភ្ជាប់ជីអយល័រប្រសិនបើនិងប្រសិនបើជីគឺ​ជា​ការ​រួបរួម​នៃ​វណ្ឌវង្ក​ដែល​ជា​គូ​មិន​មាន​គែម​រួម។
ភស្តុតាង។ ភាពចាំបាច់។ សូមឲ្យ G ធ្វើជាតួរលេខអយល័រ។ ពិចារណាចំណុចកំពូលណាមួយរបស់វា u1. អនុញ្ញាតឱ្យយើងចាកចេញពីចំនុចកំពូល u1 តាមអ័ក្សមួយចំនួន (u1, u2)។ នេះអាចត្រូវបានធ្វើដោយហេតុថា ដ្យាក្រាម G ត្រូវបានតភ្ជាប់។ ចាប់តាំងពី d-(u2) = d+(u2) វាអាចទៅរួចក្នុងការចាកចេញពីចំនុចកំពូល u2 តាមអ័ក្ស (u2, u3) . តួរលេខ G មានចំនួនកំណត់នៃចំនុចកំពូល ដូច្នេះយើងបញ្ចប់នៅចំនុចកំពូលមួយចំនួនដែលយើងនៅពីមុន។ ផ្នែកនៃខ្សែសង្វាក់ដែលចាប់ផ្តើមនិងបញ្ចប់នៅ w គឺជាផ្លូវ C1 ។ ដកធ្នូនៃវណ្ឌវង្ក C1 ចេញពីដ្យាក្រាម G . នៅក្នុងតារាងលទ្ធផល G1 (អាចផ្តាច់បាន) ដឺក្រេចូល និងចេញនៃចំនុចកំពូលដែលជាកម្មសិទ្ធិរបស់ C បានថយចុះមួយ ដឺក្រេចូល និងចេញនៃចំនុចកំពូលដែលនៅសល់មិនផ្លាស់ប្តូរទេ។ ដូច្នេះ​សម្រាប់​ចំណុច​កំពូល v នៃ​ក្រាហ្វិក C1 សមភាព d-(v) = d+(v) នឹង​កាន់។ ដូច្នេះ ក្នុង​តារាង G1 យើង​អាច​ញែក​វណ្ឌវង្ក C 2 ល។
ភាពគ្រប់គ្រាន់ត្រូវបានបង្ហាញដោយការរួមបញ្ចូលវណ្ឌវង្កទៅក្នុងវដ្តអយល័រ (សូមមើលភស្តុតាងនៃទ្រឹស្តីបទក្នុងបញ្ហា 4.2)។
ទ្រឹស្តីបទត្រូវបានបញ្ជាក់។ ប្រហែល​ជា​តួលេខ G ដែល​កំណត់​វ៉ិចទ័រ​ក្នុង​បញ្ហា​របស់​យើង​មិន​បាន​តភ្ជាប់​ទេ។ ការអនុវត្តទ្រឹស្តីបទដែលបានបញ្ជាក់ទៅផ្នែកដែលតភ្ជាប់គ្នានៃដ្យាក្រាម យើងទទួលបានភាគនៃវ៉ិចទ័រទៅជាវណ្ឌវង្ក។ ផលបូកនៃវ៉ិចទ័រដែលជាកម្មសិទ្ធិរបស់វណ្ឌវង្កមួយគឺស្មើនឹងសូន្យ។ ដូច្នេះផលបូកនៃវ៉ិចទ័រទាំងអស់គឺស្មើនឹងសូន្យ។

មុនពេលអ្នកចាប់ផ្តើមសិក្សា algorithms ដោយផ្ទាល់ អ្នកត្រូវមានចំណេះដឹងជាមូលដ្ឋានអំពីក្រាហ្វដោយខ្លួនឯង ដើម្បីយល់ពីរបៀបដែលពួកវាត្រូវបានតំណាងនៅក្នុងកុំព្យូទ័រ។ នៅទីនេះ គ្រប់ទិដ្ឋភាពទាំងអស់នៃទ្រឹស្ដីក្រាហ្វនឹងមិនត្រូវបានពិពណ៌នាលម្អិតទេ (នេះមិនត្រូវបានទាមទារ) ប៉ុន្តែមានតែភាពល្ងង់ខ្លៅប៉ុណ្ណោះដែលនឹងធ្វើឱ្យស្មុគស្មាញដល់ការរួមផ្សំនៃផ្នែកនៃការសរសេរកម្មវិធីនេះ។

ឧទាហរណ៍មួយចំនួននឹងផ្តល់នូវគំនិតស្រពិចស្រពិលនៃក្រាហ្វ។ ដូច្នេះ ក្រាហ្វធម្មតាគឺជាផែនទីផ្លូវក្រោមដី ឬផ្លូវផ្សេងទៀត។ ជាពិសេសអ្នកសរសេរកម្មវិធីម្នាក់ស្គាល់បណ្តាញកុំព្យូទ័រដែលជាក្រាហ្វផងដែរ។ រឿងធម្មតានៅទីនេះគឺវត្តមាននៃចំនុចដែលតភ្ជាប់ដោយបន្ទាត់។ ដូច្នេះនៅក្នុងបណ្តាញកុំព្យូទ័រ ចំនុចគឺជាម៉ាស៊ីនមេដាច់ដោយឡែក ហើយបន្ទាត់គឺជាប្រភេទផ្សេងគ្នានៃសញ្ញាអគ្គិសនី។ នៅក្នុងរថភ្លើងក្រោមដី ទីមួយគឺស្ថានីយ៍ ទីពីរគឺផ្លូវរូងក្រោមដីដែលដាក់នៅចន្លោះពួកគេ។ នៅក្នុងទ្រឹស្ដីក្រាហ្វ ចំណុចត្រូវបានគេហៅថា កំពូល (knots) និងបន្ទាត់ ឆ្អឹងជំនី (ធ្នូ) ដោយវិធីនេះ ក្រាហ្វគឺ​ជា​បណ្តុំ​នៃ​ចំណុច​កំពូល​ដែល​តភ្ជាប់​ដោយ​គែម។

គណិតវិទ្យាដំណើរការមិនមែនដោយខ្លឹមសារនៃវត្ថុនោះទេ ប៉ុន្តែជាមួយនឹងរចនាសម្ព័ន្ធរបស់វា ដោយអរូបីវាចេញពីអ្វីៗទាំងអស់ដែលត្រូវបានផ្តល់ឱ្យទាំងមូល។ ដោយគ្រាន់តែប្រើបច្ចេកទេសនេះ យើងអាចសន្និដ្ឋានអំពីវត្ថុមួយចំនួនដូចជាអំពីក្រាហ្វ។ ហើយចាប់តាំងពីទ្រឹស្ដីក្រាហ្វគឺជាផ្នែកមួយនៃគណិតវិទ្យា វាមិនសំខាន់ចំពោះវាទាល់តែសោះថាជាគោលការណ៍វត្ថុមួយជាអ្វី។ រឿងសំខាន់តែមួយគត់គឺថាតើវាជាក្រាហ្វ ពោលគឺថាតើវាមានលក្ខណៈសម្បត្តិដែលត្រូវការសម្រាប់ក្រាហ្វដែរឬទេ។ ដូច្នេះហើយ មុននឹងផ្តល់ឧទាហរណ៍ យើងបង្ហាញតែពីវត្ថុដែលស្ថិតក្រោមការពិចារណាតែប៉ុណ្ណោះ តាមគំនិតរបស់យើងនឹងអនុញ្ញាតឱ្យយើងបង្ហាញភាពស្រដៀងគ្នា យើងរកមើលអ្វីដែលមានលក្ខណៈធម្មតា។

ចូរយើងត្រលប់ទៅបណ្តាញកុំព្យូទ័រវិញ។ វាមាន topology ជាក់លាក់មួយ ហើយអាចត្រូវបានពិពណ៌នាជាធម្មតាថាជាចំនួននៃកុំព្យូទ័រ និងផ្លូវតភ្ជាប់ពួកវា។ តួរលេខខាងក្រោមបង្ហាញពី topology meshed ពេញលេញជាឧទាហរណ៍។

វាជាមូលដ្ឋានក្រាហ្វិក។ កុំព្យូទ័រទាំងប្រាំគឺបញ្ឈរ ហើយការតភ្ជាប់ (ផ្លូវសញ្ញា) រវាងពួកវាគឺជាគែម។ ការជំនួសកុំព្យូទ័រជាមួយចំនុចកំពូល យើងទទួលបានវត្ថុគណិតវិទ្យាមួយ - ក្រាហ្វដែលមានគែម 10 និង 5 បញ្ឈរ។ អ្នកអាចដាក់លេខបញ្ឈរតាមអំពើចិត្ត ហើយមិនចាំបាច់ជាវិធីដែលវាត្រូវបានធ្វើនៅក្នុងរូបនោះទេ។ វាគួរឱ្យកត់សម្គាល់ថានៅក្នុងឧទាហរណ៍នេះមិនមានរង្វិលជុំណាមួយត្រូវបានគេប្រើទេពោលគឺគែមដែលចាកចេញពីកំពូលហើយចូលទៅក្នុងវាភ្លាមៗប៉ុន្តែរង្វិលជុំអាចកើតឡើងក្នុងបញ្ហា។

នេះជាសញ្ញាណសំខាន់ៗមួយចំនួនដែលប្រើក្នុងទ្រឹស្តីក្រាហ្វ៖

• G = (V, E) នៅទីនេះ G គឺជាក្រាហ្វ V ជាចំនុចកំពូល ហើយ E គឺជាគែម។
• |V| - លំដាប់ (ចំនួននៃកំពូល);
• |E| - ទំហំក្រាហ្វ (ចំនួនគែម) ។

ក្នុងករណីរបស់យើង (រូបទី 1) |V|=5, |E|=10;

នៅពេលដែល vertex ផ្សេងទៀតអាចចូលបានពី vertex ណាមួយ នោះក្រាហ្វបែបនេះត្រូវបានគេហៅថា unorientedក្រាហ្វដែលបានតភ្ជាប់ (រូបភាពទី 1) ។ ប្រសិនបើក្រាហ្វត្រូវបានភ្ជាប់ ប៉ុន្តែលក្ខខណ្ឌនេះមិនពេញចិត្ត នោះក្រាហ្វបែបនេះត្រូវបានគេហៅថា តម្រង់ទិសឬតួលេខ (រូបភាពទី 2) ។

ក្រាហ្វដែលដឹកនាំ និងមិនមានទិសដៅ មានសញ្ញាណនៃកម្រិតនៃចំនុចកំពូលមួយ។ សញ្ញាប័ត្រ Vertexគឺ​ជា​ចំនួន​គែម​ដែល​ភ្ជាប់​វា​ទៅ​នឹង​ចំណុច​កំពូល​ផ្សេងទៀត។ ផលបូកនៃដឺក្រេទាំងអស់នៃក្រាហ្វគឺស្មើនឹងពីរដងនៃចំនួនគែមរបស់វា។ សម្រាប់រូបភាពទី 2 ផលបូកនៃអំណាចទាំងអស់គឺ 20 ។

នៅក្នុងតួលេខមួយ មិនដូចក្រាហ្វដែលមិនមានទិសដៅទេ វាអាចផ្លាស់ទីពីចំនុចកំពូល h ទៅ vertex s ដោយមិនមានចំនុចកំពូលកម្រិតមធ្យម លុះត្រាតែគែមមួយចាកចេញពី h ហើយចូល s ប៉ុន្តែមិនមែនផ្ទុយមកវិញទេ។

ក្រាហ្វដែលដឹកនាំមានសញ្ញាណដូចខាងក្រោមៈ

G = (V, A) ដែល V ជា​បន្ទាត់​បញ្ឈរ A ជា​គែម​តម្រង់។

ប្រភេទទីបីនៃក្រាហ្វ - លាយក្រាហ្វ (រូបភាពទី 3) ។ ពួកវាមានទាំងគែមតម្រង់ និងគ្មានទិស។ ជាផ្លូវការ ក្រាហ្វចម្រុះត្រូវបានសរសេរដូចខាងក្រោម៖ G=(V, E, A) ដែលអក្សរនីមួយៗក្នុងតង្កៀបក៏បង្ហាញពីអ្វីដែលត្រូវបានសន្មតថាពីមុនមកដែរ។

នៅក្នុងក្រាហ្វក្នុងរូបភាពទី 3 ធ្នូខ្លះត្រូវបានតម្រង់ [(e, a), (e, c), (a, b), (c, a), (d, b)] ខ្លះទៀតមិនត្រូវបានដឹកនាំ [( e, d), (e, b), (d, c)…] ។

ក្រាហ្វពីរឬច្រើននៅក្រឡេកមើលដំបូងអាចមើលទៅខុសគ្នានៅក្នុងរចនាសម្ព័ន្ធរបស់វា ដែលកើតឡើងដោយសារតែការតំណាងខុសគ្នារបស់ពួកគេ។ ប៉ុន្តែវាមិនតែងតែជាករណីនោះទេ។ ចូរយើងយកក្រាហ្វពីរ (រូបភាពទី 4) ។

ពួកវាស្មើនឹងគ្នាទៅវិញទៅមក ពីព្រោះដោយគ្មានការផ្លាស់ប្តូររចនាសម្ព័ន្ធនៃក្រាហ្វមួយ អ្នកអាចបង្កើតក្រាហ្វមួយទៀតបាន។ ក្រាហ្វបែបនេះត្រូវបានគេហៅថា អ៊ីសូម៉ូហ្វីកឧ. មានទ្រព្យសម្បត្តិថាចំនុចកំពូលណាមួយដែលមានចំនួនគែមជាក់លាក់ក្នុងក្រាហ្វមួយមានចំនុចកំពូលដូចគ្នានៅក្នុងមួយទៀត។ រូបភាពទី 4 បង្ហាញក្រាហ្វ isomorphic ពីរ។

នៅពេលដែលគែមនីមួយៗនៃក្រាហ្វត្រូវបានផ្តល់តម្លៃមួយចំនួន ហៅថាទម្ងន់នៃគែម បន្ទាប់មកក្រាហ្វបែបនេះ ផ្អាក. នៅក្នុងកិច្ចការផ្សេងៗគ្នា ការវាស់វែងប្រភេទផ្សេងៗអាចដើរតួជាទម្ងន់ ឧទាហរណ៍ ប្រវែង តម្លៃផ្លូវ។ល។ នៅក្នុងការតំណាងក្រាហ្វិកនៃក្រាហ្វ តម្លៃទម្ងន់ជាធម្មតាត្រូវបានចង្អុលបង្ហាញនៅជាប់នឹងគែម។

នៅក្នុងក្រាហ្វណាមួយដែលយើងបានពិចារណា វាអាចជ្រើសរើសផ្លូវមួយ ហើយលើសពីនេះទៅទៀតគឺច្រើនជាងមួយ។ ផ្លូវគឺ​ជា​លំដាប់​នៃ​ការ​បញ្ឈរ ដែល​នីមួយៗ​ត្រូវ​បាន​តភ្ជាប់​ទៅ​មួយ​បន្ទាប់​ដោយ​មធ្យោបាយ​នៃ​គែម​មួយ។ ប្រសិនបើចំនុចទីមួយ និងចុងក្រោយស្របគ្នា នោះផ្លូវបែបនេះត្រូវបានគេហៅថា វដ្ដ។ ប្រវែងផ្លូវត្រូវបានកំណត់ដោយចំនួនគែមដែលបង្កើតវា។ ឧទាហរណ៍ក្នុងរូបភាពទី 4.a ផ្លូវគឺជាលំដាប់ [(e), (a), (b), (c)] ។ ផ្លូវនេះគឺជាអនុក្រាហ្វមួយ ចាប់តាំងពីនិយមន័យនៃពាក្យក្រោយនេះអនុវត្តចំពោះវា ពោលគឺ៖ ក្រាហ្វ G'=(V', E') គឺជាអនុក្រាហ្វនៃក្រាហ្វ G=(V, E) លុះត្រាតែ V' និង E' ជាកម្មសិទ្ធិរបស់ V, E ។

ប្រភេទនៃក្រាហ្វអាចត្រូវបានកំណត់ដោយគោលការណ៍ទូទៅនៃការសាងសង់របស់វា (ឧទាហរណ៍ ក្រាហ្វទ្វេភាគី និងក្រាហ្វអយល័រ) ឬពួកវាអាចពឹងផ្អែកលើលក្ខណៈសម្បត្តិជាក់លាក់នៃចំនុចកំពូល ឬគែម (ឧទាហរណ៍ ក្រាហ្វដែលដឹកនាំ និងមិនមានទិសដៅ ក្រាហ្វធម្មតា )

ក្រាហ្វដែលដឹកនាំ និងមិនមានទិសដៅ

តំណភ្ជាប់(លំដាប់នៃចុងទាំងពីរនៃគែមនៃក្រាហ្វមិនសំខាន់ទេ) ត្រូវបានគេហៅថា unoriented .

ក្រាហ្វដែលគែមទាំងអស់មាន ធ្នូ(លំដាប់នៃចុងទាំងពីរនៃគែមនៃក្រាហ្វគឺសំខាន់) ត្រូវបានគេហៅថា ក្រាហ្វដែលដឹកនាំ ឬ តួលេខ .

ក្រាហ្វដែលមិនបានដឹកនាំ អាចត្រូវបានបង្ហាញជាទម្រង់ ក្រាហ្វដឹកនាំ ប្រសិនបើតំណភ្ជាប់នីមួយៗរបស់វាត្រូវបានជំនួសដោយធ្នូពីរដែលមានទិសដៅផ្ទុយ។

ក្រាហ្វរង្វិលជុំ ក្រាហ្វចម្រុះ ក្រាហ្វទទេ ពហុក្រាហ្វ ក្រាហ្វធម្មតា ក្រាហ្វពេញលេញ

ប្រសិនបើក្រាហ្វមាន រង្វិលជុំបន្ទាប់មកកាលៈទេសៈនេះត្រូវបានកំណត់យ៉ាងជាក់លាក់ដោយបន្ថែមពាក្យ "ជាមួយរង្វិលជុំ" ទៅនឹងលក្ខណៈសំខាន់នៃក្រាហ្វ ឧទាហរណ៍ "ឌីក្រាហ្វជាមួយរង្វិលជុំ" ។ ប្រសិនបើក្រាហ្វមិនមានរង្វិលជុំទេនោះពាក្យ "ដោយគ្មានរង្វិលជុំ" ត្រូវបានបន្ថែម។

លាយ ត្រូវបានគេហៅថាក្រាហ្វដែលមានគែមយ៉ាងហោចណាស់ពីរក្នុងចំណោមបីប្រភេទដែលបានរៀបរាប់ (តំណភ្ជាប់ ធ្នូ រង្វិលជុំ)។

ក្រាហ្វដែលមានតែ កំពូលភ្នំទទេ, ត្រូវ​បាន​គេ​ហៅថា ទទេ .

ពហុក្រាហ្វិក ត្រូវ​បាន​គេ​ហៅ​ថា​ក្រាហ្វិក​ដែល​គូ​នៃ​ការ​បញ្ឈរ​អាច​ត្រូវ​បាន​តភ្ជាប់​ដោយ​គែម​ច្រើន​ជាង​មួយ ដែល​មាន​ គែមជាច្រើន។ប៉ុន្តែដោយគ្មានរង្វិលជុំ។

ក្រាហ្វដោយគ្មានធ្នូ (ដែលមិនត្រូវបានតម្រង់ទិស) ដោយគ្មានរង្វិលជុំ និងគែមច្រើនត្រូវបានគេហៅថា ធម្មតា។ . ក្រាហ្វធម្មតាត្រូវបានបង្ហាញក្នុងរូបភាពខាងក្រោម។

ក្រាហ្វនៃប្រភេទដែលបានផ្តល់ឱ្យត្រូវបានគេហៅថា ពេញលេញ ប្រសិនបើវាមានគែមទាំងអស់ដែលអាចធ្វើទៅបានសម្រាប់ប្រភេទនេះ (ជាមួយនឹងសំណុំដូចគ្នានៃកំពូល)។ ដូច្នេះ នៅក្នុងក្រាហ្វធម្មតាពេញលេញ គូនៃចំនុចកំពូលផ្សេងគ្នាត្រូវបានតភ្ជាប់ដោយតំណមួយយ៉ាងពិតប្រាកដ (រូបភាពខាងក្រោម)។

ក្រាហ្វទ្វេភាគី

ក្រាហ្វត្រូវបានគេហៅថា bipartite ប្រសិនបើសំណុំនៃចំនុចកំពូលរបស់វាអាចបែងចែកជាពីររង ដូច្នេះគ្មានគែមភ្ជាប់ចំនុចកំពូលនៃសំណុំរងដូចគ្នានោះទេ។

ឧទាហរណ៍ ១សាងសង់ ពេញក្រាហ្វទ្វេភាគី។

ក្រាហ្វទ្វេភាគីពេញលេញមានពីរសំណុំនៃចំនុចកំពូល និងតំណភ្ជាប់ដែលអាចធ្វើបានទាំងអស់ដែលភ្ជាប់ចំនុចកំពូលនៃសំណុំមួយជាមួយនឹងចំនុចកំពូលនៃសំណុំផ្សេងទៀត (រូបភាពខាងក្រោម)។

ក្រាហ្វអយល័រ

យើងបានប៉ះរួចហើយ បញ្ហាអំពីស្ពានKönigsberg. ដំណោះស្រាយអវិជ្ជមានរបស់អយល័រចំពោះបញ្ហានេះបាននាំទៅដល់ការងារដែលបានបោះពុម្ពលើកដំបូងលើទ្រឹស្តីក្រាហ្វ។ បញ្ហាឆ្លងកាត់ស្ពានអាចមានលក្ខណៈទូទៅ ហើយបញ្ហាទ្រឹស្តីក្រាហ្វខាងក្រោមអាចទទួលបាន៖ តើវាអាចទៅរួចទេក្នុងការស្វែងរកវដ្ដនៅក្នុងក្រាហ្វដែលបានផ្តល់ឱ្យដែលមានចំនុចកំពូល និងគែមទាំងអស់? ក្រាហ្វដែលអាចធ្វើទៅបានត្រូវបានគេហៅថាក្រាហ្វអយល័រ។

ដូច្នេះ ក្រាហ្វអយល័រ ត្រូវ​បាន​គេ​ហៅ​ថា​ក្រាហ្វ​ដែល​វា​អាច​ទៅ​ជុំវិញ​ចំណុច​កំពូល​ទាំង​អស់ ហើយ​ក្នុង​ពេល​ជាមួយ​គ្នា​នឹង​កាត់​គែម​មួយ​តែ​ម្តង។ នៅក្នុងវា ចំនុចកំពូលនីមួយៗត្រូវតែមានត្រឹមតែចំនួនគូនៃគែមប៉ុណ្ណោះ។

ឧទាហរណ៍ ២គឺជាក្រាហ្វពេញលេញដែលមានលេខដូចគ្នា។ នគែមដែលចំនុចកំពូលនីមួយៗជាឧប្បត្តិហេតុ ក្រាហ្វអយល័រ? ពន្យល់ចម្លើយ។ ផ្តល់ឧទាហរណ៍។

ចម្លើយ។ ប្រសិនបើ ក នគឺជាចំនួនសេស បន្ទាប់មកចំនុចនីមួយៗគឺជាឧប្បត្តិហេតុ ន- ឆ្អឹងជំនីរ ១ ដុំ។ ក្នុងករណីនេះក្រាហ្វដែលបានផ្តល់ឱ្យគឺជាក្រាហ្វអយល័រ។ ឧទាហរណ៍នៃក្រាហ្វបែបនេះត្រូវបានបង្ហាញខាងក្រោម។

ក្រាហ្វធម្មតា។

ក្រាហ្វធម្មតា។ គឺ​ជា​ក្រាហ្វ​ដែល​ភ្ជាប់​គ្នា​ដែល​ចំណុច​កំពូល​ទាំងអស់​មាន​កម្រិត​ដូចគ្នា។ k. ដូច្នេះ តួរលេខឧទាហរណ៍ទី 2 បង្ហាញឧទាហរណ៍នៃក្រាហ្វធម្មតា ដែលហៅតាមកម្រិតនៃចំនុចកំពូលរបស់វា 4-regular និង 2-regular graphs ឬក្រាហ្វធម្មតានៃដឺក្រេទី 4 និងទី 2 ។

ចំនួនចំនុចកំពូលក្នុងក្រាហ្វធម្មតា។ k- សញ្ញាបត្រមិនអាចតិចជាង k+1. ក្រាហ្វធម្មតានៃដឺក្រេសេសអាចមានតែចំនួនគូនៃកំពូលប៉ុណ្ណោះ។

ឧទាហរណ៍ ៣បង្កើតក្រាហ្វធម្មតាដែលវដ្តខ្លីបំផុតមានប្រវែង 4 ។

ដំណោះស្រាយ។ យើងជជែកវែកញែកដូចតទៅ៖ ដើម្បីឱ្យរយៈពេលនៃវដ្តបំពេញលក្ខខណ្ឌដែលបានផ្តល់ឱ្យ វាត្រូវបានទាមទារឱ្យចំនួនចំនុចកំពូលនៃក្រាហ្វជាពហុគុណនៃបួន។ ប្រសិនបើចំនួនបញ្ឈរគឺបួន នោះក្រាហ្វដែលបង្ហាញក្នុងរូបភាពខាងក្រោមនឹងត្រូវបានទទួល។ វាទៀងទាត់ ប៉ុន្តែវដ្តខ្លីបំផុតរបស់វាមានប្រវែង 3 ។

បង្កើនចំនួនចំនុចកំពូលដល់ប្រាំបី (ចំនួនបន្ទាប់គឺគុណនឹងបួន)។ យើងភ្ជាប់ចំនុចកំពូលជាមួយគែម ដូច្នេះដឺក្រេនៃចំនុចកំពូលគឺស្មើនឹងបី។ យើងទទួលបានក្រាហ្វខាងក្រោមដែលបំពេញលក្ខខណ្ឌនៃបញ្ហា។

ក្រាហ្វ hamiltonian

ក្រាហ្វ Hamilton ត្រូវបានគេហៅថាក្រាហ្វដែលមានវដ្ត Hamiltonian ។ វដ្ត Hamilton ត្រូវ​បាន​គេ​ហៅ​ថា​វដ្ដ​សាមញ្ញ​មួយ​ដែល​ឆ្លង​កាត់​ចំណុច​កំពូល​ទាំង​អស់​នៃ​ក្រាហ្វ​ដែល​កំពុង​ពិចារណា។ ដូច្នេះដើម្បីនិយាយឱ្យសាមញ្ញ ក្រាហ្វ Hamiltonian គឺជាក្រាហ្វដែលចំនុចកំពូលទាំងអស់អាចឆ្លងកាត់បាន ហើយចំនុចកំពូលនីមួយៗត្រូវបានធ្វើម្តងទៀតតែម្តងគត់ក្នុងអំឡុងពេលឆ្លងកាត់។ ឧទាហរណ៍នៃក្រាហ្វ Hamiltonian មាននៅក្នុងរូបភាពខាងក្រោម។

ឧទាហរណ៍ 4ផ្តល់ក្រាហ្វិកទ្វេភាគីដែលក្នុងនោះ ន- ចំនួនបញ្ឈរពីសំណុំ ក, ក ម- ចំនួនបញ្ឈរពីសំណុំ ខ. តើ​ក្រាហ្វ​ក្នុង​ករណី​ណា​ជា​ក្រាហ្វ Eulerian ហើយ​ក្នុង​ករណី​ណា​ជា​ក្រាហ្វ Hamiltonian?

នៅក្នុងជំពូកមុន យើងបានបង្ហាញពីលទ្ធផលសំខាន់ៗមួយចំនួននៃទ្រឹស្តីនៃក្រាហ្វដែលមិនដឹកនាំ។ ទោះជាយ៉ាងណាក៏ដោយ ក្រាហ្វដែលមិនបានដឹកនាំគឺមិនគ្រប់គ្រាន់ដើម្បីពិពណ៌នាអំពីស្ថានភាពមួយចំនួននោះទេ។ ជាឧទាហរណ៍ នៅពេលតំណាងឱ្យផែនទីចរាចរណ៍ដែលមានក្រាហ្វដែលគែមរបស់វាត្រូវគ្នានឹងផ្លូវ ទិសត្រូវតែកំណត់ទៅគែមដើម្បីបង្ហាញពីទិសដៅដែលអាចអនុញ្ញាតបាននៃចលនា។ ឧទាហរណ៍មួយទៀតគឺកម្មវិធីកុំព្យូទ័រដែលយកគំរូតាមក្រាហ្វដែលគែមតំណាងឱ្យលំហូរនៃការគ្រប់គ្រងពីសំណុំនៃការណែនាំទៅមួយផ្សេងទៀត។ នៅក្នុងការតំណាងនៃកម្មវិធីនេះ គែមក៏ត្រូវតែត្រូវបានផ្តល់ការតំរង់ទិសដើម្បីចង្អុលបង្ហាញទិសដៅនៃលំហូរវត្ថុបញ្ជា។ ឧទាហរណ៍មួយទៀតនៃប្រព័ន្ធរូបវន្តដែលទាមទារក្រាហ្វដឹកនាំដើម្បីតំណាងគឺសៀគ្វីអគ្គិសនី។ ការអនុវត្តក្រាហ្វដែលដឹកនាំ និងក្បួនដោះស្រាយពាក់ព័ន្ធត្រូវបានពិភាក្សានៅក្នុងជំពូក។ ១១-១៥។

ជំពូកនេះបង្ហាញពីលទ្ធផលចម្បងនៃទ្រឹស្តីនៃក្រាហ្វដឹកនាំ។ សំណួរទាក់ទងនឹងអត្ថិភាពនៃខ្សែសង្វាក់អយល័រតម្រង់ទិស និងវដ្ត Hamiltonian ត្រូវបានពិភាក្សា។ ដើមឈើតម្រង់ទិស និងការតភ្ជាប់របស់វាជាមួយខ្សែសង្វាក់អយល័រតម្រង់ទិសក៏ត្រូវបានពិចារណាផងដែរ។

៥.១. និយមន័យ និងគោលគំនិតជាមូលដ្ឋាន

ចូរចាប់ផ្តើមដោយការណែនាំនិយមន័យ និងគោលគំនិតជាមូលដ្ឋានមួយចំនួនទាក់ទងនឹងក្រាហ្វដែលដឹកនាំ។

ក្រាហ្វដែលដឹកនាំមានពីរឈុត៖ សំណុំកំណត់ V ដែលធាតុរបស់វាត្រូវបានគេហៅថាបញ្ឈរ និងសំណុំ E កំណត់ដែលធាតុរបស់វាត្រូវបានគេហៅថាគែមឬធ្នូ។ ធ្នូនីមួយៗត្រូវបានភ្ជាប់ជាមួយគូបញ្ឈរ។

និមិត្តសញ្ញាត្រូវបានប្រើដើម្បីកំណត់ចំណុចកំពូល ហើយនិមិត្តសញ្ញាត្រូវបានប្រើដើម្បីកំណត់អ័ក្ស។ ប្រសិនបើ , បន្ទាប់មកត្រូវបានគេហៅថាចុង , ដែលជាកន្លែងដែល - កំពូលដំបូង , - ចុង vertex ។ ធ្នូទាំងអស់ដែលមានចំនុចចាប់ផ្តើម និងចុងដូចគ្នា ត្រូវបានគេហៅថាប៉ារ៉ាឡែល។ ធ្នូត្រូវបានគេហៅថារង្វិលជុំ ប្រសិនបើចំនុចកំពូលនៃឧប្បត្តិហេតុគឺជាចំនុចចាប់ផ្តើម និងចុងរបស់វា។

នៅ​ក្នុង​ការ​តំណាង​ក្រាហ្វិក​នៃ​ក្រាហ្វ​ដែល​បាន​តម្រង់​ទិស​ ចំណុច​បញ្ឈរ​ត្រូវ​បាន​តំណាង​ដោយ​ចំណុច​ ឬ​រង្វង់​ ហើយ​គែម​ (ធ្នូ​) ត្រូវ​បាន​តំណាង​ដោយ​ផ្នែក។

បន្ទាត់តភ្ជាប់ចំណុច ឬរង្វង់តំណាងឱ្យចំណុចបញ្ចប់របស់ពួកគេ។ លើសពីនេះ ធ្នូត្រូវបានចាត់តាំងទិសមួយ ដែលបង្ហាញដោយព្រួញដែលចង្អុលពីចំណុចចាប់ផ្តើមទៅកំពូលចុង។

ឧទាហរណ៍ ប្រសិនបើបែបនោះជារបស់ពួកគេ) ក្រាហ្វដែលដឹកនាំអាចត្រូវបានតំណាងដោយរូបភព។ ៥.១. នៅក្នុងក្រាហ្វនេះ - ធ្នូប៉ារ៉ាឡែល និង - រង្វិលជុំ។

អង្ករ។ ៥.១. ក្រាហ្វតម្រង់ទិស។

ធ្នូ​មួយ​ត្រូវ​បាន​គេ​និយាយ​ថា​ជា​ឧប្បត្តិហេតុ​ដល់​ចុង​ចុង​របស់​វា។ បញ្ឈរត្រូវបានគេហៅថានៅជាប់ ប្រសិនបើពួកវាជាស្ថានីយសម្រាប់ធ្នូមួយ។ ប្រសិនបើធ្នូមានចំនុចកំពូលនៃស្ថានីយធម្មតា នោះពួកវាត្រូវបានគេហៅថាជាប់។

ធ្នូត្រូវបានគេហៅថាចេញពីចំនុចកំពូលដំបូងរបស់វា ហើយចូលដល់ចំនុចចុងក្រោយរបស់វា។ ចំនុចកំពូលត្រូវបានគេនិយាយថាដាច់ពីគេ ប្រសិនបើវាមិនមានឧប្បត្តិហេតុ arcs ។

កម្រិតនៃចំនុចកំពូលគឺជាចំនួននៃឧបទ្ទវហេតុ arcs ទៅវា។ នៅក្នុងដឺក្រេនៃ vertex គឺជាចំនួននៃ arcs ចូលទៅក្នុង V] ហើយ out-degree គឺជាចំនួននៃ arcs ចេញ។ និមិត្តសញ្ញា និង b" បង្ហាញពីកម្រិតទាបបំផុត និងក្នុងដឺក្រេនៃក្រាហ្វដែលបានដឹកនាំ។ ស្រដៀងគ្នានេះដែរ និមិត្តសញ្ញាបង្ហាញពីកម្រិតអតិបរមាក្រៅដឺក្រេ និងក្នុងដឺក្រេរៀងៗខ្លួន។

សំណុំនៃ vertex ណាមួយត្រូវបានកំណត់ដូចខាងក្រោម: . ឧទាហរណ៍នៅក្នុងក្រាហ្វក្នុងរូបភព។ ៥.១.

ចំណាំថារង្វិលជុំបង្កើនពាក់កណ្តាលដឺក្រេនៃទាំងការចូលនិងចេញនៃកំពូលនេះ។ ការអះអាងខាងក្រោមគឺជាផលវិបាកនៃការពិតដែលថាធ្នូនីមួយៗកើនឡើង 1 ផលបូកនៃ semidegrees ទាំងការបញ្ចូល និងលទ្ធផលនៃក្រាហ្វដែលដឹកនាំ។

ទ្រឹស្តីបទ ៥.១. នៅក្នុងក្រាហ្វដែលដឹកនាំដោយធ្នូ

ផលបូកនៃដឺក្រេ = ផលបូកនៃដឺក្រេ = m ។

ក្រាហ្វរង និងក្រាហ្វដែលបានបង្កើតនៃក្រាហ្វដែលដឹកនាំត្រូវបានកំណត់តាមរបៀបដូចគ្នានឹងក្រាហ្វដែលមិនបានដឹកនាំ (វគ្គ 1.2) ។

ក្រាហ្វដែលមិនដឹកនាំដែលកើតចេញពីការដកចេញការតំរង់ទិសពីធ្នូនៃក្រាហ្វដែលដឹកនាំ G ត្រូវបានគេហៅថាក្រាហ្វមិនដឹកនាំ G ហើយត្រូវបានតំណាងដោយ .

ផ្លូវដឹកនាំនៃក្រាហ្វដែលដឹកនាំគឺជាលំដាប់កំណត់នៃចំនុចកំពូល

អ្វីជាធ្នូនៃក្រាហ្វ G. ផ្លូវបែបនេះជាធម្មតាត្រូវបានគេហៅថា - ផ្លូវតម្រង់ទិស ហើយចំនុចកំពូលដំបូងគឺជាចំនុចកំពូលចុងក្រោយនៃផ្លូវ ហើយចំនុចកំពូលផ្សេងទៀតទាំងអស់គឺខាងក្នុង។ ចំនុចចាប់ផ្តើម និងចុងនៃផ្លូវដែលដឹកនាំត្រូវបានគេហៅថា ចំនុចបញ្ចប់របស់វា។ ចំណាំថា ធ្នូ ហើយហេតុដូចនេះហើយ ចំនុចកំពូលអាចលេចឡើងច្រើនជាងមួយដងនៅក្នុងផ្លូវដែលដឹកនាំ។

ផ្លូវតម្រង់ទិសត្រូវបានគេនិយាយថាបើកចំហ ប្រសិនបើចំនុចចុងរបស់វាខុសគ្នា បើមិនដូច្នោះទេវាត្រូវបានគេហៅថាបិទ។

ផ្លូវតម្រង់ទិសត្រូវបានគេហៅថា ផ្លូវតម្រង់ទិស ប្រសិនបើអ័ក្សទាំងអស់របស់វាខុសគ្នា។ ផ្លូវតម្រង់ទិសត្រូវបានបើក ប្រសិនបើចំណុចបញ្ចប់របស់វាខុសគ្នា បើមិនដូច្នោះទេ វាត្រូវបានបិទ។

ផ្លូវតម្រង់ទិសបើកចំហត្រូវបានគេហៅថាផ្លូវតម្រង់ទិស ប្រសិនបើចំនុចកំពូលទាំងអស់របស់វាខុសគ្នា។

ខ្សែសង្វាក់តម្រង់ទិសបិទត្រូវបានគេហៅថា វដ្ដតម្រង់ទិស ឬវណ្ឌវង្ក ប្រសិនបើចំនុចកំពូលរបស់វា លើកលែងតែស្ថានីយមានភាពខុសគ្នា។

ក្រាហ្វដែលដឹកនាំត្រូវបានគេនិយាយថាជា acyclic ឬគ្មានវណ្ឌវង្កប្រសិនបើវាមិនមានវណ្ឌវង្ក។ ឧទាហរណ៍ ក្រាហ្វដែលដឹកនាំក្នុងរូបភាពទី 1 គឺ acyclic ។ ៥.២.

អង្ករ។ ៥.២. ក្រាហ្វដែលដឹកនាំដោយអាសុីគ្លី។

អង្ករ។ ៥.៣. ក្រាហ្វដឹកនាំដែលភ្ជាប់យ៉ាងរឹងមាំ។

លំដាប់នៃចំនុចកំពូលនៅក្នុងក្រាហ្វដែលដឹកនាំ G ត្រូវបានគេហៅថាផ្លូវនៅក្នុង G ប្រសិនបើវាជាផ្លូវនៅក្នុងក្រាហ្វដែលមិនបានដឹកនាំ។ ឧទាហរណ៍ លំដាប់នៅក្នុងក្រាហ្វក្នុងរូប។ 5.2 គឺជាផ្លូវមួយ ប៉ុន្តែមិនតម្រង់ទិសទេ។

ខ្សែសង្វាក់ ផ្លូវ និងវដ្តនៃក្រាហ្វដែលដឹកនាំត្រូវបានកំណត់ស្រដៀងគ្នា។

ក្រាហ្វដែលដឹកនាំត្រូវបានគេនិយាយថាត្រូវបានតភ្ជាប់ ប្រសិនបើក្រាហ្វដែលមិនបានដឹកនាំត្រូវបានភ្ជាប់។

អនុក្រាហ្វនៃក្រាហ្វដែលដឹកនាំ G ត្រូវបានគេហៅថាធាតុផ្សំនៃក្រាហ្វ G ប្រសិនបើវាជាធាតុផ្សំនៃក្រាហ្វ

ចំនុចកំពូលនៃក្រាហ្វដែលដឹកនាំ G ត្រូវបានគេនិយាយថាមានទំនាក់ទំនងយ៉ាងខ្លាំងប្រសិនបើមានផ្លូវដឹកនាំពី និងត្រលប់ទៅ G ។ ប្រសិនបើត្រូវបានភ្ជាប់យ៉ាងខ្លាំងទៅនោះ ច្បាស់ណាស់គឺត្រូវបានភ្ជាប់យ៉ាងរឹងមាំទៅ . ចំនុចកំពូលនីមួយៗត្រូវបានភ្ជាប់យ៉ាងរឹងមាំទៅនឹងខ្លួនវា។

ប្រសិនបើ vertex ត្រូវបានភ្ជាប់យ៉ាងខ្លាំងទៅនឹង vertex នោះ ដូចដែលវាងាយស្រួលមើល នោះ vertex ត្រូវបានភ្ជាប់យ៉ាងខ្លាំងទៅនឹង vertex ដូច្នេះហើយ ក្នុងករណីនេះ គេគ្រាន់តែនិយាយថា vertex ត្រូវបានភ្ជាប់យ៉ាងខ្លាំង។

ក្រាហ្វដែលដឹកនាំត្រូវបានគេនិយាយថាមានទំនាក់ទំនងខ្លាំង ប្រសិនបើចំនុចកំពូលទាំងអស់របស់វាត្រូវបានភ្ជាប់យ៉ាងខ្លាំង។ ឧទាហរណ៍ ក្រាហ្វក្នុងរូប។ ៥.៣.

ក្រាហ្វដែលភ្ជាប់ខ្លាំងបំផុតនៃក្រាហ្វដែលដឹកនាំ G ត្រូវបានគេហៅថាជាសមាសធាតុភ្ជាប់យ៉ាងរឹងមាំរបស់ G ។ ប្រសិនបើក្រាហ្វដែលដឹកនាំត្រូវបានភ្ជាប់យ៉ាងរឹងមាំ នោះវាមានធាតុផ្សំដែលតភ្ជាប់ខ្លាំងតែមួយគឺខ្លួនវាផ្ទាល់។

ពិចារណាក្រាហ្វដែលដឹកនាំ។ វាងាយស្រួលក្នុងការមើលឃើញថា ចំនុចកំពូលនីមួយៗរបស់វាជាកម្មសិទ្ធិរបស់ធាតុផ្សំដែលភ្ជាប់យ៉ាងរឹងមាំនៃក្រាហ្វ G។ ដូច្នេះហើយ សំណុំនៃចំនុចកំពូលនៃសមាសធាតុដែលភ្ជាប់គ្នាខ្លាំងបង្កើតបានជាភាគថាសនៃចំនុចកំពូល Y នៃក្រាហ្វ។

អង្ករ។ ៥.៤. ក្រាហ្វនិង condensation របស់វា។

ឧទាហរណ៍ ក្រាហ្វដែលដឹកនាំក្នុងរូប។ 5.4, ​​​a មាន​សមាសភាគ​តភ្ជាប់​យ៉ាង​ខ្លាំង​បី​ជាមួយ​នឹង​សំណុំ vertex និង​បង្កើត​ជា​ភាគថាស​នៃ​សំណុំ vertex នៃ​ក្រាហ្វ​ដែល​បាន​ដឹកនាំ។

គួរឱ្យចាប់អារម្មណ៍ ក្រាហ្វដែលដឹកនាំអាចមានធ្នូដែលមិនត្រូវបានរួមបញ្ចូលនៅក្នុងសមាសធាតុដែលមានទំនាក់ទំនងខ្លាំងណាមួយនៃក្រាហ្វ។ ជាឧទាហរណ៍ គ្មានធាតុផ្សំដែលភ្ជាប់គ្នាខ្លាំង រួមបញ្ចូលធ្នូនៅក្នុងក្រាហ្វក្នុងរូប។ ៥.៤, ក.

ដូច្នេះ ទោះបីជាទ្រព្យសម្បត្តិ "ភ្ជាប់យ៉ាងរឹងមាំ" រួមបញ្ចូលការបំបែកសំណុំ vertex នៃក្រាហ្វក៏ដោយ វាអាចនឹងមិនបង្កើតការបំបែកសំណុំនៃធ្នូនោះទេ។

សហជីព ចំនុចប្រសព្វ ផលបូក mod 2 និងប្រតិបត្តិការផ្សេងទៀតនៅលើក្រាហ្វដែលបានដឹកនាំត្រូវបានកំណត់យ៉ាងពិតប្រាកដដូចគ្នាទៅនឹងករណីនៃក្រាហ្វដែលមិនដឹកនាំ (វិ។ 1.5) ។

ក្រាហ្វដែលកើតចេញពីការកន្ត្រាក់នៃធ្នូទាំងអស់នៃសមាសធាតុភ្ជាប់ខ្លាំងនៃក្រាហ្វដែលដឹកនាំ G ត្រូវបានគេហៅថាក្រាហ្វិចនៃក្រាហ្វ G. ការបង្រួមនៃក្រាហ្វដែលបង្ហាញក្នុងរូបភព។ 5.4, ​​​​a, ត្រូវបានបង្ហាញនៅក្នុងរូបភព។ 5.4 ខ។

ចំនុចកំពូលនៃក្រាហ្វត្រូវគ្នាទៅនឹងសមាសធាតុដែលភ្ជាប់យ៉ាងរឹងមាំនៃក្រាហ្វ G ហើយត្រូវបានគេហៅថារូបភាពបង្រួមនៃសមាសធាតុ។

ចំណាត់ថ្នាក់ និងលេខ cyclomatic នៃក្រាហ្វដែលដឹកនាំគឺដូចគ្នាទៅនឹងក្រាហ្វដែលមិនបានដឹកនាំដែលត្រូវគ្នា។ នេះ​មាន​ន័យ​ថា ប្រសិនបើ​ក្រាហ្វ​ដែល​បាន​ដឹកនាំ G មាន​អ័ក្ស​បញ្ឈរ និង​សមាសធាតុ នោះ​ចំណាត់ថ្នាក់ និង​លេខ​ស៊ីក្លូ​នៃ​ក្រាហ្វ G ត្រូវ​បាន​ផ្តល់​ដោយ

ឥឡូវនេះ យើងកំណត់ក្រាហ្វដែលបានភ្ជាប់យ៉ាងតិចបំផុត និងសិក្សាពីលក្ខណៈសម្បត្តិមួយចំនួនរបស់វា។

ក្រាហ្វដែលដឹកនាំ G ត្រូវបានគេនិយាយថាត្រូវបានភ្ជាប់តិចតួចបំផុតប្រសិនបើវាត្រូវបានភ្ជាប់យ៉ាងខ្លាំង ហើយការដកធ្នូណាមួយដកហូតវាពីទ្រព្យសម្បត្តិដែលបានភ្ជាប់យ៉ាងខ្លាំងរបស់វា។

អង្ករ។ ៥.៥. ក្រាហ្វដែលដឹកនាំដោយភ្ជាប់តិចតួចបំផុត។

ជាឧទាហរណ៍ ក្រាហ្វដែលបង្ហាញក្នុងរូប។ ៥.៥.

ជាក់ស្តែង ក្រាហ្វដែលភ្ជាប់គ្នាតិចតួចបំផុត មិនអាចមានធ្នូ និងរង្វិលជុំស្របគ្នាបានទេ។

យើងដឹងថាក្រាហ្វដែលមិនមានទិសដៅត្រូវបានភ្ជាប់យ៉ាងតិចបំផុត ប្រសិនបើវាជាមែកធាង (ឧទាហរណ៍ 2.13)។ តាមទ្រឹស្តីបទ 2.5 មែកធាងមួយមានចំនុចកំពូលយ៉ាងតិចពីរនៃដឺក្រេ 1។ ដូច្នេះហើយ ក្រាហ្វដែលមិនទាក់ទងគ្នាតិចតួចបំផុតមានចំនុចកំពូលពីរនៃដឺក្រេ 1។

អនុញ្ញាតឱ្យយើងបង្កើតលទ្ធផលស្រដៀងគ្នាសម្រាប់ក្រាហ្វដែលដឹកនាំ។ កម្រិតនៃចំនុចកំពូលណាមួយនៃក្រាហ្វដែលដឹកនាំដោយភ្ជាប់យ៉ាងខ្លាំងត្រូវតែមានយ៉ាងហោចណាស់ 2 ព្រោះថាចំនុចកំពូលនីមួយៗត្រូវតែមានអ័ក្សចេញ និងចូល។ នៅក្នុងទ្រឹស្ដីខាងក្រោម យើងបង្ហាញថាក្រាហ្វដែលភ្ជាប់គ្នាយ៉ាងតិចបំផុតមានចំនុចកំពូលពីរនៃដឺក្រេ 2។

គែម​មួយ​គឺ​ជា​គូ​បញ្ឈរ​តាម​លំដាប់។ ក្រាហ្វដែលទិសដៅនៃគែមនីមួយៗរបស់វាត្រូវបានចង្អុលបង្ហាញត្រូវបានគេហៅថា តម្រង់ទិស.

ជាក់ស្តែង កម្មវិធីសម្រាប់ការប្រកួត។ ជាឧទាហរណ៍ ព្រួញចេញពីក្រុមចាញ់ទៅអ្នកឈ្នះ ដូច្នេះក្រាហ្វដែលដឹកនាំបង្ហាញមិនត្រឹមតែថាអ្នកណាលេងជាមួយអ្នកណាទេ ប៉ុន្តែអ្នកណាឈ្នះ។

វាក៏អាចធ្វើទៅបានដើម្បីកំណត់លំដាប់ ឬទំនាក់ទំនងចំណូលចិត្តដោយក្រាហ្វដឹកនាំ។

ឧទាហរណ៍, នៅក្នុងក្រាហ្វក្បួនដោះស្រាយចំនុចកំពូលនៃក្រាហ្វត្រូវគ្នា។ ប្រតិបត្តិការកំពុងត្រូវបានអនុវត្តហើយធ្នូ (គែមតម្រង់ទិស) ត្រូវគ្នានឹង ភាពអាស្រ័យទិន្នន័យ(ឧ. ត្រូវការធាតុបញ្ចូលអ្វីខ្លះ ដើម្បីអនុវត្តប្រតិបត្តិការ)។

ឧទាហរណ៍ នៅក្នុងការវាយតម្លៃគំរូស្មុគស្មាញ (ឧទាហរណ៍នៅក្នុងភូមិសាស្ត្រ) ទិសដៅនៃគែមបង្ហាញពីចំណូលចិត្ត។ ប្រព័ន្ធចំណូលចិត្តធម្មតាមិនគួរមានវដ្តទេ។

Tanya Natasha

ដូច្នេះអ្នកអាចធ្វើការជ្រើសរើសបានជានិច្ច បើមិនដូច្នេះទេ អ្នកត្រូវពិចារណាឡើងវិញនូវប្រព័ន្ធនៃចំណូលចិត្ត។

ផ្លូវ​មួយ។

ផែនទីផ្លូវដែលមានទិសដៅនៃការធ្វើដំណើរផ្តល់នូវឧទាហរណ៍ពិសេសនៃក្រាហ្វដែលដឹកនាំ។ ដើម្បីដោះស្រាយជាមួយផ្លូវពីរផ្លូវ ជំនួសឱ្យផ្លូវមួយ (ឬជំនួសឱ្យគែមដែលមិនមានទិសដៅមួយ) យើងណែនាំគែមតម្រង់ពីរដែលតភ្ជាប់កំពូលដូចគ្នា និងមានទិសដៅផ្ទុយ។

សំណួរសួរថា តើផ្លូវក្នុងទីក្រុងអាចតម្រង់ទិសក្នុងស្ថានភាពបែបណា ដែលអាចបើកបរពីចំណុចណាមួយទៅកន្លែងណាមួយដោយមិនបំពានច្បាប់ចរាចរណ៍នៅតាមដងផ្លូវ។

នៅក្នុងភាសានៃទ្រឹស្ដីក្រាហ្វ វាត្រូវបានបង្កើតដូចខាងក្រោម៖ ក្រោមលក្ខខណ្ឌអ្វី គែមនៃក្រាហ្វ G អាចតម្រង់ទិស ដូច្នេះសម្រាប់គូណាមួយនៃកំពូលរបស់វា មានផ្លូវតម្រង់ទិសតភ្ជាប់ពួកវា?

វាច្បាស់ណាស់ថាក្រាហ្វនីមួយៗត្រូវតែភ្ជាប់ ប៉ុន្តែនេះមិនគ្រប់គ្រាន់ទេ។

គែម E = (A, B) នឹងត្រូវបានគេហៅថា គែមតភ្ជាប់, ឬ isthmusប្រសិនបើវាជាផ្លូវតែមួយគត់ពី A ទៅ B (ឬផ្ទុយមកវិញ) ។

គែមតភ្ជាប់បែងចែកបញ្ឈរទាំងអស់នៃក្រាហ្វជាពីរឈុត៖ ចំណុចដែលអាចទៅដល់ពី A ដោយមិនឆ្លងកាត់គែម E និងដែលអាចទៅដល់ពី B ដោយមិនឆ្លងកាត់ E ។ ក្រាហ្វក្នុងករណីនេះមានពីរផ្នែក G 1 និង G 2 តភ្ជាប់តែដោយគែម E (រូបភាព a និង a+1) ។

នៅលើផែនទីនៃទីក្រុង ឆ្អឹងជំនីរតភ្ជាប់គឺជាផ្លូវហាយវេតែមួយគត់ដែលតភ្ជាប់ផ្នែកដាច់ដោយឡែកនៃទីក្រុង។ វាច្បាស់ណាស់ថា ប្រសិនបើចរាចរណ៍ផ្លូវមួយត្រូវបានបង្កើតឡើងនៅលើមហាវិថីបែបនេះ នោះនឹងមិនមានផ្លូវឆ្លងកាត់ពីផ្នែកមួយនៃទីក្រុងទៅផ្នែកមួយទៀតនោះទេ។

ប្រសិនបើគែម E i = (A i , B i) មិនតភ្ជាប់ទេ នោះមានផ្លូវមួយទៀតដែលភ្ជាប់ A i និង B i ហើយមិនឆ្លងកាត់ E i ។ ដូច្នេះគែមបែបនេះនឹងត្រូវបានគេហៅថាគែមរង្វិល។

fig.2 ការភ្ជាប់រូបភព។ 2+1 ចុងក្រោយ (តភ្ជាប់) រូបភាព 2+2 វដ្ត

ឆ្អឹងជំនីរ

ទ្រឹស្តីបទ ១ ប្រសិនបើ ក G- ក្រាហ្វដែលបានតភ្ជាប់ បន្ទាប់មកវាតែងតែអាចធ្វើទៅបានដើម្បីតម្រង់ទិសរង្វង់ពី ជី ដោយទុកគែមតភ្ជាប់ដោយមិនបង្វែរទិសដៅ ដូច្នេះគូនៃចំនុចកំពូលណាមួយនៅក្នុងក្រាហ្វនេះអាចត្រូវបានតភ្ជាប់ដោយផ្លូវដែលដឹកនាំ។

សម្រាប់ផែនការទីក្រុង សេចក្តីថ្លែងការណ៍នេះអាចត្រូវបានបង្កើតដូចខាងក្រោម៖ ប្រសិនបើចរាចរណ៍ពីរផ្លូវគឺនៅសល់តែលើស្ពាន (ផ្តល់ថាស្ពាននេះគឺជាស្ពានតែមួយគត់ឆ្លងកាត់ទន្លេ) និងនៅលើផ្លូវស្លាប់ បន្ទាប់មកនៅលើផ្លូវផ្សេងទៀតទាំងអស់ ចរាចរណ៍ផ្លូវមួយ អាចត្រូវបានបង្កើតឡើងតាមរបៀបដែលការដឹកជញ្ជូនផ្តល់នូវការទំនាក់ទំនងគ្រប់ផ្នែកនៃទីក្រុង។

យើងអាចបញ្ជាក់ទ្រឹស្តីបទនេះដោយបង្ហាញវិធីដើម្បីតំរង់ទិសក្រាហ្វិកឱ្យបានត្រឹមត្រូវ។ តោះជ្រើសរើសចូល ជី គែមបំពាន អ៊ី \u003d (A, B) . ប្រសិនបើ ក អ៊ី - គែមតភ្ជាប់ វានឹងនៅតែពីរចំហៀង ហើយបន្ទាប់មកវានឹងអាចទៅពី ប៉ុន្តែ ទៅ អេ និងខាងក្រោយ (រូបភាព 2+3) ។

fig.2+3 រូប។ 2+4

ប្រសិនបើ ក អ៊ី គឺជាគែមរង្វិល បន្ទាប់មកវាត្រូវបានរួមបញ្ចូលនៅក្នុងវដ្តមួយចំនួន ពី ដែលអ្នកអាចកំណត់ទិសរង្វិល (រូបភាព ២+៤)។

ឧបមាថាយើងបានតម្រង់ទិសផ្នែកខ្លះរួចហើយ ហ រាប់ ជី ដូច្នេះពីចំនុចកំពូលណាមួយនៃក្រាហ្វ ហ អ្នក​អាច​ទៅ​កាន់​ចំណុច​កំពូល​ផ្សេង​ទៀត​ដោយ​គោរព​តាម​ច្បាប់​ចរាចរណ៍​ផ្លូវ​មួយ​។ ចាប់តាំងពីក្រាហ្វ ជី ត្រូវបានភ្ជាប់បន្ទាប់មកក៏បាន ហ ផ្គូផ្គងក្រាហ្វិកទាំងមូល g, ឬមានគែមមួយ។ អ៊ី \u003d (A, B), ដែលមិនមែនជាកម្មសិទ្ធិ ហ ប៉ុន្តែ​មួយ​នៃ​ចំណុច​កំពូល​របស់​វា​និយាយ​ ប៉ុន្តែ , ជាកម្មសិទ្ធិ ហ .

ប្រសិនបើ ក អ៊ី - ឆ្អឹងជំនីរតភ្ជាប់ AB បន្ទាប់មកវានឹងនៅតែពីរភាគី។ បន្ទាប់មកសម្រាប់ចំណុចកំពូលណាមួយ។ X រាប់ ហ មនុស្សម្នាក់អាចស្វែងរកខ្សែសង្វាក់តម្រង់ទិស រ ការភ្ជាប់ X ជាមួយ A ដែលមានន័យថា (តាមរយៈគែម អ៊ី ) និងជាមួយ អេ . ត្រលប់ពីកំពូល អេ នៅ​លើ​គែម អ៊ី អ្នកអាចទៅ ប៉ុន្តែ ហើយបន្ទាប់មក - តាមខ្សែសង្វាក់តម្រង់ទិស Z - ពី ប៉ុន្តែ ទៅ X (រូបភាព ក+៥)។ ការភ្ជាប់ អ៊ី ទៅ ហ យើងនឹងទទួលបានក្រាហ្វិកភាគច្រើន ជី ជាមួយនឹងលក្ខណៈសម្បត្តិដែលត្រូវការ។ ប្រសិនបើគែម អ៊ី \u003d (A, B) គឺ​ជា​វដ្ដ វា​ជា​របស់​វដ្ដ​មួយ​ចំនួន ពី . យើងកំណត់ទិសដៅសម្រាប់ ពី ពី ប៉ុន្តែ ពីមុន អេ និងបន្តបន្ទាប់ទៀត។ ពី ដល់កំពូលទីមួយ ឃ ពី ពី ជាកម្មសិទ្ធិរបស់ ហ (រូបភាព a+6)។

អង្ករ។ a+5 រូប។ a+6

តោះបន្ថែមគែមទាំងអស់នេះទៅ ហ . អនុញ្ញាតឱ្យ X - កំពូលបំពានពី ហ , ក នៅ - ចំណុចកំពូលណាមួយ។ ពី ; មនុស្សម្នាក់អាចស្វែងរកខ្សែសង្វាក់តម្រង់ទិស រ , ជាកម្មសិទ្ធិ ហ និងការភ្ជាប់ X ជាមួយ ប៉ុន្តែ ហើយបន្ទាប់មកតាម ពី ទៅកំពូល នៅ ពី ពី . ត្រឡប់មកពី នៅ អ្នកអាចដើរតាម ពី ទៅកំពូល ឃ , និងពីវា - ជាកម្មសិទ្ធិ ហ ខ្សែសង្វាក់តម្រង់ទិស Z - ពី ឃ ទៅ X . ដូច្នេះក្រាហ្វដឹកនាំដែលទទួលបានដោយការបន្ថែមទៅ ហ គែមរង្វង់ដែលបានបញ្ជាក់ ពី បំពេញលក្ខខណ្ឌចាំបាច់ផងដែរ។ ការបន្តដំណើរការនេះ ទីបំផុតយើងតម្រង់ទិសក្រាហ្វដើមតាមវិធីដែលត្រូវការ ជី .

ដឺក្រេ Vertex ។

សម្រាប់ក្រាហ្វដែលដឹកនាំ យើងមាននៅចំនុចកំពូលនីមួយៗ លេខ p(A) នៃការចេញ និងលេខ p*(A) នៃគែមចូល។ ចំនួនគែមសរុបគឺ៖

N \u003d p (A 1) + p (A 2) + ... + p (A n) \u003d p * (A 1) + p * (A 2) + ... + p * (A n)

មានប្រភេទផ្សេងៗនៃក្រាហ្វដែលដឺក្រេ vertex មានលក្ខណៈសម្បត្តិពិសេសមួយចំនួន។ ការរាប់ត្រូវបានគេហៅថា ដូចគ្នាប្រសិនបើដឺក្រេនៃចំនុចកំពូលរបស់វាស្មើនឹងចំនួនដូចគ្នា r: សម្រាប់ចំនុចកំពូលនីមួយៗ A:

p (A) = p * (A) = r

លំហាត់មួយ។

បង្កើតក្រាហ្វដឹកនាំដូចគ្នានៃដឺក្រេ r = 2 ជាមួយ n = 2,6,7,8 បញ្ឈរ។

ទំនាក់ទំនង។

ទំនាក់ទំនងនិងក្រាហ្វ។

ប្រព័ន្ធគណិតវិទ្យាណាមួយទាក់ទងនឹងសំណុំនៃវត្ថុ ឬធាតុមួយចំនួន។ (សញ្ញា៖ ពិជគណិត ធរណីមាត្រ)

ដើម្បី​បង្កើត​ទ្រឹស្ដី​គណិត​វិទ្យា យើង​ត្រូវ​ការ​មិន​ត្រឹម​តែ​ធាតុ​ទាំង​នេះ​ខ្លួន​ឯង​ប៉ុណ្ណោះ​ទេ ប៉ុន្តែ​ក៏​ត្រូវ​ការ​ផង​ដែរ។ ទំនាក់ទំនងរវាង​ពួកគេ។ (ឧទាហរណ៍៖ សម្រាប់លេខ a> b; ក្នុងធរណីមាត្រ - សមភាពនៃត្រីកោណ // បន្ទាត់; នៅក្នុងទ្រឹស្តីសំណុំ - សមភាព និងការរួមបញ្ចូលនៃសំណុំ។ )

ទំនាក់ទំនងទាំងអស់នេះទាក់ទងនឹងវត្ថុពីរដូច្នេះពួកគេត្រូវបានគេហៅថា ទំនាក់ទំនងគោលពីរឬសាមញ្ញ ទំនាក់ទំនងឧទាហរណ៍ មានទំនាក់ទំនងប្រភេទផ្សេងទៀត។ ទំនាក់ទំនងអន្តរជាតិទាក់ទងនឹងវត្ថុបី។ (ឧទាហរណ៍ ចំណុច A ស្ថិតនៅចន្លោះចំណុច B និង C)។

ចូរយើងណែនាំនិយមន័យទូទៅនៃទំនាក់ទំនងគោលពីរ R: аRв - в គឺទាក់ទងនឹង R ទៅ a ។

ឧទាហរណ៍ ទំនាក់ទំនង a > b មានន័យថា b ជាកម្មសិទ្ធិរបស់សំណុំនៃលេខទាំងអស់តិចជាង a

តាមពិត ក្រាហ្វដែលដឹកនាំនីមួយៗ G កំណត់ទំនាក់ទំនងមួយចំនួននៅក្នុងសំណុំនៃចំនុចកំពូលរបស់វា។ សមាមាត្រនេះអាចត្រូវបានសរសេរជា: аGв។ វាមានន័យថាក្រាហ្វមានគែមតម្រង់ពី a ទៅ b ។

លក្ខខណ្ឌពិសេស។

អនុញ្ញាតឱ្យទំនាក់ទំនង R មួយចំនួន។ ប្រសិនបើធាតុ a មានទំនាក់ទំនង R ជាមួយខ្លួនវា នោះវាត្រូវគ្នានឹងរង្វិលជុំនៅក្នុងក្រាហ្វ។

ទំនាក់ទំនង R ដែលលក្ខខណ្ឌ аRв ពេញចិត្ត សម្រាប់ណាមួយ a, ត្រូវ​បាន​គេ​ហៅថា ឆ្លុះបញ្ចាំង.

ប្រសិនបើលក្ខខណ្ឌ aRv មិនពេញចិត្តសម្រាប់ធាតុណាមួយនោះ R ត្រូវបានហៅ អាកប្បកិរិយាប្រឆាំងនឹងការឆ្លុះបញ្ចាំង.ក្នុងករណីនេះ គ្មានចំនុចកំពូលនៃក្រាហ្វមានរង្វិលជុំទេ។

សម្រាប់ទំនាក់ទំនងនីមួយៗ R អាចកំណត់បាន។ សមាមាត្របញ្ច្រាស R *សន្មតថា аR * в ប្រសិនបើ ហើយប្រសិនបើ аRв ។

តាមនិយមន័យនៃទំនាក់ទំនងបញ្ច្រាស វាអាចត្រូវបានគេមើលឃើញថាប្រសិនបើក្រាហ្វ G ដែលត្រូវគ្នានឹង R មានគែម (a, b) នោះក្រាហ្វ G * ដែលត្រូវគ្នានឹង R * ត្រូវតែមានគែម (c, a) ។ នៅក្នុងពាក្យផ្សេងទៀតក្រាហ្វ G * គឺបញ្ច្រាសទៅ G, i.e. ក្រាហ្វដែលមានគែមដូចគ្នានឹង G ប៉ុន្តែតម្រង់ទិសផ្ទុយ។

ទំនាក់ទំនងត្រូវបានគេហៅថា ស៊ីមេទ្រីប្រសិនបើពី аRв ធ្វើតាម вРа ។

ទំនាក់ទំនងស៊ីមេទ្រីត្រូវគ្នាទៅនឹងក្រាហ្វដែលមានគែមមិនកំណត់; ផ្ទុយទៅវិញ ក្រាហ្វដែលមានគែមមិនតម្រង់កំណត់ទំនាក់ទំនងស៊ីមេទ្រីមួយចំនួន។

ទំនាក់ទំនងត្រូវបានគេហៅថា antisymmetricប្រសិនបើវាធ្វើតាមពី аRв នោះវាពិតជាមិនកាន់ក្នុង Rа ទេ។ ក្រាហ្វទំនាក់ទំនង Antisymmetric មិនមានគែមតម្រង់ទិស ឬផ្ទុយគ្នាដែលភ្ជាប់គូបញ្ឈរដូចគ្នា; លើសពីនេះទៅទៀតមិនមានរង្វិលជុំនៅលើពួកវាទេ i.e. ទំនាក់ទំនងទាំងនេះគឺប្រឆាំងនឹងការឆ្លុះបញ្ចាំង។

សមាមាត្រ អន្តរកាលប្រសិនបើវាធ្វើតាមលក្ខខណ្ឌពីរ aRb និង bRc នោះ aRc ។

ក្រាហ្វនៃទំនាក់ទំនងអន្តរកាលមានលក្ខណសម្បត្តិដូចខាងក្រោមៈ សម្រាប់គូនៃគែមនីមួយៗ (a, b), (c, c) មាន ការបិទគែម។ ការ​អនុវត្ត​លក្ខណៈ​នេះ​ម្តង​ហើយ​ម្តង​ទៀត យើង​សន្និដ្ឋាន​ថា ប្រសិនបើ​ក្រាហ្វ​នេះ​មាន​ផ្លូវ​តម្រង់​ពី​ចំណុច​កំពូល X ទៅ​ចំណុច​កំពូល Y នោះ​ក៏​មាន​គែម​តម្រង់ (x, y) ដែរ។

សន្មតថាមានក្រាហ្វ G ដែលមានគែមតម្រង់ដែលមិនមែនជាអន្តរកាល។ ក្នុងគ្រប់ករណីទាំងអស់ ក្រាហ្វ G ដែលដឹកនាំអាចធ្វើអន្តរកាលដោយបន្ថែមគែមតម្រង់ទៅវា រហូតដល់ការបិទត្រូវបានភ្ជាប់សម្រាប់គ្រប់គែមជាប់គ្នារបស់វា។ ក្រាហ្វថ្មី G m ដែលទទួលបានត្រូវបានគេហៅថា ការបិទបណ្តោះអាសន្នរាប់ G

ទំនាក់ទំនងសមភាព។

ទំនាក់​ទំនង​សមមូល ដែល​ជា​ធម្មតា​ត្រូវ​បាន​បង្ហាញ​ដោយ ~ មាន​លក្ខណៈ​សម្បត្តិ​បី​ដូច​ខាង​ក្រោម៖

មួយ) ការ​ឆ្លុះ​បញ្ចាំង : a ~ a;

២). ស៊ីមេទ្រី៖ ពី a ~ ទៅ z ទៅ ~ a;

៣). Transitivity : ពី a ~ ទៅ និង ទៅ ~ c Þ a ~ c ។

តាមការពិត ទំនាក់ទំនងសមភាព គឺជាលក្ខណៈទូទៅនៃទ្រព្យសម្បត្តិសមភាព។

ទំនាក់ទំនងសមមូលណែនាំភាគថាសទៅក្នុងសំណុំនៃកំពូល ថ្នាក់សមមូលមិនជាប់គ្នា។.

សូមឱ្យ B i ជាសំណុំនៃចំនុចកំពូលនៃក្រាហ្វសមមូល G ដែលស្មើនឹងចំនុចកំពូល i ។ បន្ទាប់មកចំនុចកំពូលទាំងអស់ដែលជាកម្មសិទ្ធិរបស់ B i ត្រូវបានភ្ជាប់ដោយគែម i.e. នៅក្នុង i - ក្រាហ្វពេញលេញ G i ។ នៅចំនុចកំពូលនីមួយៗនៃក្រាហ្វបែបនេះមានរង្វិលជុំមួយ។ ក្រាហ្វ G បំបែកទៅជាសំណុំនៃសមាសធាតុដែលបានតភ្ជាប់ G i ។

លំដាប់ដោយផ្នែក។

អាកប្បកិរិយា លំដាប់ដោយផ្នែកគឺ (នៅលើឧទាហរណ៍នៃសំណុំ):

មួយ) ការឆ្លុះបញ្ចាំង៖ A Ê A

២). Transitivity: ប្រសិនបើ A Ê B និង B Ê C Þ A Ê C

៣). អត្តសញ្ញាណ៖ ប្រសិនបើ A Ê B និង B Ê Az A = B

ទំនាក់ទំនងដាក់បញ្ចូលយ៉ាងតឹងរឹង -

មួយ) ការប្រឆាំងនឹងការឆ្លុះបញ្ចាំង៖ អេអេអេមិនដែលកើតឡើងទេ។

២). Transitivity: ប្រសិនបើ A É B និង B É C នោះ A É C

ទំនាក់ទំនងការបញ្ជាទិញ(ក្នុងន័យតឹងរឹង) ត្រូវបានគេហៅថា លំដាប់តឹងរ៉ឹង a> b ដែលបន្ថែមលើលក្ខខណ្ឌមុន ខាងក្រោមនេះក៏មាន៖

លក្ខខណ្ឌពេញលេញ។សម្រាប់ធាតុដែលមិនស្របគ្នាទាំងពីរនៅក្នុង និង a ទំនាក់ទំនងមួយក្នុងចំណោមទំនាក់ទំនងទាំងពីរ a>b ឬ b>a តែងតែពេញចិត្ត។

ជាធម្មតា ក្រាហ្វដែលបានបញ្ជាដោយផ្នែកត្រូវបានបង្ហាញក្នុងទម្រង់ដែលបានបញ្ជាទិញ។ ដោយសារសម្រាប់គែមណាមួយ (a, b) និង (b, c) មានគែមបិទ (a, c) វាអាចត្រូវបានលុបចោល។

ក្រាហ្វិករាបស្មើ។

លក្ខខណ្ឌសម្រាប់ក្រាហ្វប្លង់។

រាប់ Kuratovsky K 3.3

បញ្ហាក្រាហ្វអំពីផ្ទះបីនិងអណ្តូងបី

រាប់ Kuratovsky K ៥

ក្រាហ្វទាំងពីរនេះមិនរាបស្មើទេ!

ផ្នែកបន្ថែមក្រាហ្វ- បញ្ឈរថ្មីត្រូវបានដាក់នៅលើគែមមួយចំនួន ដូច្នេះគែមទាំងនេះ

បានក្លាយជាខ្សែសង្វាក់បឋមដែលមានគែមជាច្រើន។

ប្រតិបត្តិការបញ្ច្រាសត្រង់ចំនុចដែលបំបែកចេញពីខ្សែសង្វាក់បឋមត្រូវបានគេហៅថា ការបង្ហាប់ក្រាហ្វ។

ទ្រឹស្តីបទ Kuratovsky

ដើម្បីឱ្យក្រាហ្វមានរាងសំប៉ែត វាចាំបាច់ និងគ្រប់គ្រាន់ដែលវាមិនមានក្រាហ្វណាមួយនៅក្នុងខ្លួនដែលអាចត្រូវបានបង្ហាប់ទៅជាក្រាហ្វ K 3.3 ឬក្រាហ្វ K 5 ។

រូបមន្តអយល័រ

យើងនឹងពិចារណាក្រាហ្វប្លង់ដែលបង្កើតនៅលើយន្តហោះ បណ្តាញពហុកោណ. នេះមានន័យថាគែមនៃគំនូសប្លង់ G បង្កើតជាសំណុំពហុកោណនៅជាប់គ្នា ដោយបែងចែកប្លង់ទៅជាពហុកោណ។

វាធ្វើតាមនិយមន័យនៃក្រាហ្វពហុកោណដែលពួកគេត្រូវបានតភ្ជាប់។ យើង​ក៏​ទាមទារ​ដែរ​ថា​គ្មាន​ពហុកោណ​ស្ថិត​នៅ​ខាង​ក្នុង​មួយ​ទៀត​ទេ។ គែមព្រំដែននៃពហុកោណបែបនេះបង្កើតជាវដ្ដ ជួនកាលគេហៅថា វដ្តអប្បបរមា. ផ្នែកនៃយន្តហោះដែលរុំព័ទ្ធក្នុងពហុកោណត្រូវបានគេហៅថា ក្រាហ្វមុខ. ក្រាហ្វក៏មាន វដ្តអតិបរមា C 1ជុំវិញក្រាហ្វទាំងមូលជាមួយនឹងមុខរបស់វា។ យើង​នឹង​ពិចារណា​ផ្នែក​នៃ​យន្តហោះ​ដែល​ស្ថិត​នៅ​ខាង​ក្រៅ C 1 ក៏​ដូច​ជា​មុខ​ក្រាហ្វ​ដែល​មាន​ព្រំដែន C 1 - គ្មានទីបញ្ចប់មុខ F ¥ ។

បញ្ជាក់ដោយ

ចំនួនបញ្ឈរ គែម និងមុខ ពហុកោណអវកាស។.

ទ្រឹស្តីបទអយល័រ

c − p + r = 2

ភស្តុតាង៖រូបមន្តគឺជាក់ស្តែងសម្រាប់ពហុកោណដែលមានគែម n ។ ពិតហើយ n បញ្ឈរ និង n គែម ក៏ដូចជាមុខពីរ F 1 F ¥

យើងបន្ថែមមុខថ្មីទៅក្រាហ្វដែលមានមុខ r ដោយគូរតាមមុខ F ¥ ខ្សែសង្វាក់បឋមមួយចំនួនដែលភ្ជាប់ចំនុចកំពូលពីរនៃក្រាហ្វអតិបរមា G. ប្រសិនបើធ្នូនេះមានគែម r នោះយើងត្រូវបន្ថែម r - 1 បញ្ឈរថ្មី និងមួយថ្មី មុខ។ ប៉ុន្តែ​បន្ទាប់មក

c' - p' + r' = (c + r - 1) - (p + r) + (r + 1) = c - p + r (= 2!)

ដោយសម្មតិកម្មនៃការបញ្ចូល។

តំណាងម៉ាទ្រីស។

1. ម៉ាទ្រីសឧប្បត្តិហេតុ A.

ក) សម្រាប់ក្រាហ្វដែលមិនបានដឹកនាំ ម៉ាទ្រីសឧប្បត្តិហេតុគឺ​ជា​ម៉ាទ្រីស​ដែល​ជួរ​ដេក​ត្រូវ​គ្នា​នឹង​ជួរ​ឈរ ហើយ​ជួរ​ឈរ​ត្រូវ​គ្នា​នឹង​គែម។ ធាតុ​ម៉ាទ្រីស​គឺ​ស្មើ​នឹង 1 ប្រសិន​បើ​ចំណុច​កំពូល​ប៉ះ​នឹង​គែម។ បើមិនដូច្នោះទេធាតុម៉ាទ្រីសយកតម្លៃ 0 ។

ខ) សម្រាប់ក្រាហ្វដែលដឹកនាំ ធាតុនៃម៉ាទ្រីសឧប្បត្តិហេតុគឺ +1 នៅពេលដែលឧប្បត្តិហេតុ vertex ទៅធ្នូគឺជាចំនុចចាប់ផ្តើមនៃធ្នូ (ឧ. ធ្នូកើតចេញពីចំនុចកំពូលនេះ)។ ធាតុគឺ -1 នៅពេលដែលធ្នូចូលកំពូល។ ប្រសិនបើចំនុចកំពូលមិនកើតឡើងចំពោះធ្នូទេ នោះធាតុម៉ាទ្រីសគឺ 0 ។

2. ម៉ាទ្រីសនៃវដ្ត C ។

ក) សម្រាប់ក្រាហ្វដែលមិនមានទិសដៅ ជួរដេកនៃម៉ាទ្រីសវដ្តត្រូវគ្នាទៅនឹងវដ្តសាមញ្ញនៃក្រាហ្វ ហើយជួរឈរត្រូវគ្នាទៅនឹងគែមរបស់វា។ ធាតុម៉ាទ្រីស a ij = 1 ប្រសិនបើវដ្ត С i មានគែម e j ។ បើមិនដូច្នោះទេ ij = 0 ។

ខ) សម្រាប់ក្រាហ្វដែលដឹកនាំ a ij =1, -1 ឬ 0 អាស្រ័យលើថាតើការតំរង់ទិសនៃវដ្ត C i និងធ្នូ e j គឺដូចគ្នា ឬផ្ទុយ ឬវដ្តនេះមិនមាន arc e j ទាល់តែសោះ។

3. ម៉ាទ្រីស vertex adjacency matrix (ឬធម្មតាម៉ាទ្រីស adjacency) V គឺជាម៉ាទ្រីសដែលជួរដេក និងជួរឈរត្រូវគ្នានឹងចំនុចកំពូល ហើយធាតុម៉ាទ្រីស a ij ក្នុងករណីក្រាហ្វមិនដឹកនាំគឺស្មើនឹងចំនួនគែមតភ្ជាប់ចំនុចកំពូល i និង j . សម្រាប់ក្រាហ្វដែលដឹកនាំ ធាតុ a ij គឺស្មើនឹងចំនួនគែមដែលដឹកនាំពី vertex i ទៅ vertex j ។

ទ្រឹស្តីបទ Onovye ទាក់ទងនឹងតំណាងម៉ាទ្រីសនៃក្រាហ្វ។

1) ចំណាត់ថ្នាក់ (ចំនួនអតិបរមានៃជួរឈរឯករាជ្យលីនេអ៊ែរ) នៃម៉ាទ្រីសឧប្បត្តិហេតុ A នៃក្រាហ្វដែលបានតភ្ជាប់ (បានដឹកនាំ និងមិនបានដឹកនាំ) ដែលមានចំនុចកំពូល n គឺស្មើនឹង (n-1)។

២). ចំណាត់ថ្នាក់នៃម៉ាទ្រីសវដ្ត C នៃក្រាហ្វដែលភ្ជាប់ជាមួយគែម m និង n បញ្ឈរគឺ (m-n+1) ។

ឧទាហរណ៍នៃការប្រើប្រាស់ម៉ាទ្រីសជាប់គ្នា។

ការធ្វើផែនទីខាងក្រោមបង្ហាញថាក្រាហ្វ G 1 និង G 2 គឺអ៊ីសូម៉ូហ្វីក

នៅក្នុងម៉ាទ្រីសនៅជាប់គ្នា ជួរដេក និងជួរឈរត្រូវបានអនុញ្ញាតក្នុងពេលដំណាលគ្នា ដែលអាចត្រូវបានអនុវត្តដោយប្រើការបំប្លែងភាពស្រដៀងគ្នា និងម៉ាទ្រីសបំប្លែង។

A 2 \u003d PA 1 P", កន្លែងណា

P = ឬ p ij =d p(i),j (និមិត្តសញ្ញា Kroneker)

និង R" គឺជាម៉ាទ្រីសបំប្លែង។

ការស្វែងរកម៉ាទ្រីស P អាចជាល្បិច។

isomorphism នៃ G 1 និង G 2 មានន័យថា A 1 និង A 2 មាន ​​eigenvalues ​​ដូចគ្នា។ ទោះយ៉ាងណាក៏ដោយ លក្ខខណ្ឌនេះមិនគ្រប់គ្រាន់ទេ (ឧទាហរណ៍ខាងក្រោម)។