Графтың анықтамасы мен негізгі ұғымдары
Анықтама
Граф — объектілер жиынтығының (төбелер) және олардың арасындағы байланыстардың (қабырғалар) абстрактілі көрінісі. G:=(V, E).
| Түрі | Сипаттамасы |
|---|
| Бағытталмаған | Байланыс екі жаққа бірдей |
| Бағытталған (орграф) | Қабырғалар бағытты (доға) |
Анықтама
Көршілес матрица — N×N кесте: A[i][j]=1 егер i мен j байланысса. Бағытталмаған графта СИММЕТРИЯЛЫ.
Анықтама
Байланысқан граф — кез келген екі төбенің арасында жол бар. Ағаш — байланысқан және циклсіз граф.
Деңгей: Оңай Симметриялықты тексеру
Берілді: A→B, B→C доғалары бар бағытталған граф.
Табу керек: матрица симметриялы ма?
Шешуі:
A→B бар, бірақ B→A жоқ — сондықтан матрица симметриялы ЕМЕС.
Жауабы: жоқ, симметриялы емес.