Графический способ задания графов.
Способы задания графов
2. Матрица смежности (для вершин).
Для графа:
Для орграфа:
3. Матрица инциденций.
Для графа:
Для орграфа:
4. Функциональный способ задания графов.
, 
- функция окрестности вершин. 
Для орграфа:
- функция положительной полуокрестности.
- функция отрицательной полуокрестности.
Два графа (орграфа) 
и 
изоморфны, если существует взаимнооднозначная функция 
такая, что:
1) если 
и 
смежны в 
, то 
и 
смежны в 
;
2) если 
и 
смежны в , то 
и 
смежны в .
Изоморфизм обладает свойствами рефлексивности, симметричности, транзитивности, следовательно обладает свойством эквивалентности на множестве графов.
Примеры
| 
| Графы не являются изоморфными.
|
Матрица инциденций и матрица смежности задают граф с точностью до изоморфизма.
Количественная или качественная характеристика, неизменная для всех изоморфных между собой графов называется инвариантом графа. Поиск этих инвариантов – основная задача теории графов.
