Графтың анықтамасы мен негізгі ұғымдары
Instagram-дағы «достар» желісін, метро картасындағы бекеттерді, немесе отбасы шежіресін елестет — бәрінде де «нүктелер» (адамдар, бекеттер) және оларды байланыстыратын «сызықтар» (достық, жол) бар. Дәл осындай құрылымды информатикада ГРАФ деп атайды. Бұл сабақта графтың негізгі ұғымдарын және оны компьютерде қалай сақтауға болатынын үйренеміз.
1736 жылы Леонард Эйлер Кёнигсберг қаласындағы жеті көпірді бір рет қана басып өту мүмкін бе деген басқатырғышты шешу үшін алғаш рет графтарды қолданды. Термин өзі кейінірек, 1936 жылы, венгр математигі Денеш Кениг тарапынан енгізілді. Бүгінде граф теориясы әлеуметтану, биология, химия, тіпті навигация қосымшаларында кеңінен қолданылады.
Граф — объектілер жиынтығының (төбелер) және олардың арасындағы байланыстардың (қабырғалар) абстрактілі көрінісі. Әрбір қабырға ЕКІ төбені байланыстырады.
Графты G:=(V, E) түрінде белгілейді, мұндағы V — төбелер жиыны, E — қабырғалар жиыны.
Метро картасында поезд бір бағытта ғана жүре ме, әлде екі бағытта да ма? Дәл осы сұрақ графтың түрін анықтайды:
| Түрі | Сипаттамасы |
|---|---|
| Бағытталмаған граф | Қабырғаның бағыты жоқ — байланыс екі жаққа бірдей |
| Бағытталған граф (орграф) | Қабырғалар бағытты, «доға» деп аталады |
| Аралас граф | Бағытталған да, бағытталмаған да қабырғадан тұрады |
Терминологиясында бірнеше маңызды ұғым бар:
| Ұғым | Сипаттамасы |
|---|---|
| Сыбайлас төбелер | Қабырғамен тікелей қосылған екі төбе |
| Төбенің дәрежесі | Сол төбеден шыққан қабырғалар саны |
| Ілмек | Төбені өзімен-өзі байланыстыратын қабырға |
| Қарапайым граф | Ілмегі де, еселі қабырғасы да жоқ граф |
| Мультиграф | Кем дегенде екі төбе бір қабырғадан АРТЫҚ қабырғамен қосылған граф |
Ал төбелерден төбеге «жол жүру» ұғымдарында да нақты айырмашылық бар:
| Ұғым | Сипаттамасы |
|---|---|
| Маршрут | Көршілес төбелерді қосатын төбелер мен қабырғалардың тізбегі |
| Тізбек | Төбелері бірдей ЕМЕС (қайталанбайтын) маршрут |
| Цикл | Соңғы төбеден басқа барлық төбесі әртүрлі болатын ТҰЙЫҚТАЛҒАН тізбек |
Байланысқан граф — кез келген екі төбенің арасында жол бар граф. Ағаш — байланысқан ЖӘНЕ циклсіз граф. Салмағы бар граф — әр қабырғасына сандық сипаттама (мыс. қашықтық) бекітілген граф.
Графты компьютерде «суреттемей», сандар түрінде қалай сақтаймыз? Ең қарапайым тәсіл — кесте (матрица):
Көршілес (байланыс) матрица — N×N өлшемді квадрат матрица (N — төбелер саны).
A[i][j]=1, егер i мен j төбелері байланысса; A[i][j]=0, әйтпесе.
Берілді: A, B, C, D төбелері, қабырғалары: A-B, A-C, B-C, B-D.
Неге матрица симметриялы? Бағытталмаған графта байланыс екі бағытта бірдей — A мен B байланысса, B мен A да байланысады.
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 1 | 0 | 1 | 1 |
| C | 1 | 1 | 0 | 0 |
| D | 0 | 1 | 0 | 0 |
Берілді: A, B, C, D төбелері, доғалары: A→B, A→C, B→C, C→A, D→B.
Неге СИММЕТРИЯЛЫ ЕМЕС? A→C бар, C→A да бар, сондықтан ол екі ұяшық та 1. Бірақ B→A ЖОҚ, тек A→B бар, сондықтан A[B][A]=0, ал A[A][B]=1 — матрица симметриялы емес.
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 0 | 0 | 1 | 0 |
| C | 1 | 0 | 0 | 0 |
| D | 0 | 1 | 0 | 0 |
Жауабы: бағытталмаған граф матрицасы ӘРҚАШАН симметриялы, бағытталған граф матрицасы ЖАЛПЫ АЛҒАНДА симметриялы емес.
Берілді: N көпір арасындағы жолдардың байланыс матрицасы (бағытталмаған граф).
Табу керек: байланыс саны (қабырғалар саны).
Неге 2-ге бөлеміз? Бағытталмаған графта әр байланыс матрицада ЕКІ РЕТ көрінеді (A[i][j]=1 ЖӘНЕ A[j][i]=1), сондықтан бірлер санын 2-ге бөлу керек.
with open('input.txt', "r") as f:
N = int(f.readline())
A = [tuple(int(x) for x in line.split()) for line in f]
z = 0
for i in range(N):
for j in range(N):
if A[i][j] == 1:
z += 1
with open('output.txt', "w") as h:
h.write(str(z // 2))Матрица үлкен графтарда ЖАДЫНЫ ЫСЫРАП ЕТЕДІ (көп нөл сақтайды), сондықтан басқа тәсілдер де бар:
Қабырғалар тізімі — бірінші жолда төбелер саны мен қабырғалар саны, келесі әр жолда — байланысқан екі төбе (керек болса, салмағымен).
5 6
1 2 10
1 3 7
2 4 8
2 5 9
3 4 8
4 5 6Ал инциденттік матрица — қабырға мен төбе арасындағы байланысты көрсететін N×M өлшемді (N — төбе, M — қабырға саны) кесте. Ол күрделірек, бірақ графтағы циклдерді табуды жеңілдетеді.
- Граф — төбелер мен оларды байланыстыратын қабырғалардан тұратын абстрактілі құрылым.
- Бағытталмаған граф — байланыс екі бағытта; бағытталған (орграф) — тек бір бағытта (доға).
- Көршілес матрица — графты N×N кесте түрінде сақтау тәсілі; бағытталмағанда симметриялы.
- Қабырғалар тізімі мен инциденттік матрица — графты сақтаудың балама тәсілдері.