АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Формальді

Мысал.

Анықтама. бағытталған граф деп жиындар жұбын айтады, мұндағы - төбелер жиыны, - доғалар жиыны ( реттелген жұптар).

Анықтама. аралас граф деп жиындар жұбын айтады, мұндағы - төбелер жиыны, - қабырғалар мен доғалар жиыны.

Ескерту. Алдағы уақытта тек бағытталмаған графтарды қарастырамыз.

Графтарды келесідей беруге болады:

1. Графикалық

2. Сыбайлас матрицасы – өлшемді кесте, мұнда -нші жолдың -нші бағанасымен қиылысуында 1 қойылады, кері жағдайда – 0, .

- реттелмеген жұп болғандықтан, сыбайлас матрицасы диагоналіне қарасты симмериялы болады.

Мысал.

Формальді

Мысал.

, мұндағы ;

Немесе графтың ең қысқа жазылуы: 1:2,4; 2:5; 3:4; 4:5.

Негізгі анықтамалар:

1) Егер , онда төбелері сыбайлас, және қабырғасына инцидентті деп аталады.

2) қабырғасы төбесіне және төбесіне инцидентті деп аталады.

3) Екі қабырға сыбайлас деп аталады, егер оларға инцидент болатын ортақ төбе табылса.

4) төбесінің дәрежесі деп, сол төбеге инцидент болатын қабырғалар санын айтады. Егер , онда - оңаша төбе, ал егер , онда - аспалы төбе деп аталады.

5) Тізбе – сыбайлас қабырғалардың тізбегі.

6) Цикл – тұйықталған тізбе.

7) Жай цикл – төбелері қайталанбайтын цикл.

8) Гамильтон циклі – барлық төбелерден өтетін жай цикл.

9) Эйлер циклі – барлық қабырғалардан тек бір рет өтетін цикл (Теорема. Егер граф байланысты болса және барлық төбелерінің дәрежелері жұп сан болса, онда графта эйлер циклі табылады).

10) Тізбе ұзындығы – тізбедегі қабырғалар саны.

11) Төбелердің арақашықтығы – бұл төбелерді қосатын ең қысқа тізбенің ұзындығы.

12) Графтың диаметрі – ең алыс орналасқан екі төбенің арақашықтығы.

13) графын графтың ішкі графы деп айтады, егер , . ішкі графы графының меншікті ішкі графы аталады, егер .

14) графтың барлық төбелерінен тұратын ішкі графын остовты деп атайды.

15) Графтың төбесін алып тастағанда, оған инцидент болатын қабырғалары да алынады.

16) Графтың қабырғасын алып тастағанда, оған инцидент болатын төбелері қалады.

17) графы - графының толықтауышы деп аталады, егер , , - толық граф.

Бағытталмаған графтардың түрлері:

1) Регуляр граф – барлық төбелерінің дәрежелері бірдей болатын граф.

2) Жұпты теру – төбелердің дәрежелері 1-ге тең болатын регуляр граф.

3) Байланысты граф – кез келген екі төбесі тізбемен байланысты болатын граф.

4) Толық граф – барлық мүмкін болатын қабырғаларынан тұратын граф.

5) Ағаш – циклі жоқ байланысты граф.

6) графы - екібөлікті, егер , , және . (Кёниг теоремасы: Граф екібөлікті болады сонда тек сонда, егер оның ішінде тақ ұзындықты цикл болмаса)

Бағытталған графтар

Берілу тәсілдері – бағытталмаған графтармен бірдей.

Ескерту. Жалпы жағдайдағы сыбайлас матрицасы симметриялы болмайды.

Негізгі анықтамалары:

1) Төбенің шығуынын жарты дәрежесі – бұл төбеден шығатын доғаларының саны, кірудің жарты дәрежесі - төбеге кіретін доғалардың саны.

2) Сыбайлас доғалар деп, біреуінің аяғы мен екіншісінің басы сәйкес келетін доғаларды айтады.

3) Жол – сыбайлас доғалардың тізбегі.

4) Контур – тұйық жол.

5) Ілмек – ­ доғасы.

6) Орграфы бағыты бар граф болады, егер жұбынан шығады (ілмектер жоқ).

7) Турнир – кез келген екі төбенің арасында тек бір ғана доға болса (ілмектер жоқ).

ДС 2. Байланысты графтар.Ағаштар. Орман

Дата добавления: 2015-09-27 | Просмотры: 640 | Нарушение авторских прав