| Бақылау сұрақтары:
1. Байланысқан компоненттер дегеніміз не?
2. Графта жолды іздеу қалай жүзеге асырылады?
3. Қоспалы граф дегеніміз не?
4. Жолдың басы дегеніміз не?
5. Жолдың соңы дегеніміз не?
Дәріс №11. Эйлер циклдары және шынжырлар
1.Жұп графтар
2.Эйлер графы
Жұп графтар
Граф төбелерін ұстайтын байланыссыз граф бөлігін қарастырамыз. Мұнда l1 , l2 , …,ln арқылы номерленген P төбелерден тұратын G графы болсын. Әрбір графтың H G бөлігіне P -өлшемді векторды (a1, a2 , …, an ) ноль бірден тұратын (1,егер l1 H, 0, егер l1 H ) H граф бөлігінің мінездемелік бөлігін аламыз. Бұл қатынас өзара бір мәнді сәйкестік. H1 және H2 граф бөліктерінің модуль екі бойынша қосындысы H1 H2 олардың {0.1} коэффициенттер жиынының үстіне графтың барлық бөліктерінің жиыны сызықтық кеңістікті құрайды: кезкелген граф бөлігін H- ты бірге көбейткенде H- ты береді, ал H -ты нольге көбейткенде құр граф бөлігін қырларды ұстамайтын бөлігін береді және G графының бөлектенген төбелерінен тұрады. G графының бөліктерінің кеңістігі және оның граф бөліктерінің мінездемелік векторлардың кеңістігі изоморфты және оның өлшемі P болады. Граф бөліктерінің бір қырлық жиыны базис бола алады.
Егер оның барлық төбелерінің дәрежесі жұп болса, ондай графты жұп граф дейміз. Кез келген элементарлық тізбек (циклден басқа) жұп графты тізбекке жатпайтын қырын ұзартсақ, онда тізбектің соңғы дәрежесі бір және гафта оның дәрежесі екіден кем еместігі шығады. Егер граф шекті болса, онда тізбекті ұзартсақ шекті реті арқылы біз екінші өтілген төбеге келеміз, алынған бөліктегі тізбек элементарлық циклді құрайды, шығарғаннан кейін жұп граф қалады, себебі барлық дәрежелер жұп санға өзгереді (екі циклдің төбелері үшін және 0 циклге жатпайтын төбелер үшін).
Достарыңызбен бөлісу: |
