Нехай G - позначений граф з n вершинами і m ребрами. Визначимо матрицю суміжності A (G) у такий спосіб:
Матриця суміжності квадратна, розміру n 'n.
Можна помітити, що матриця суміжності є симетричною, і кількість одиниць в кожному рядку дорівнює ступеню вершини, якої відповідає цей рядок. По матриці суміжності легко побудувати графічне представлення графа.
Приклад 4.6. Побудувати граф по матриці суміжності
Можна визначити матрицю інцидентності I (G). має n рядків і m стовпців, елементи якої задаються наступним чином:
Приклад 4.7. Розглянемо граф з прикладу 4.6, позначивши ребра.
У кожному рядку матриці інцидентності тільки два елементи відмінні від 0 (або один, якщо ребро є петлею). Тому такий спосіб опису виявляється неекономним. Ставлення инцидентности можна задати також списком ребер графа. Кожен рядок цього списку відповідає ребру, в ній записані номери вершин, інцидентних йому.
Приклад 4.8. Розглянемо граф з прикладу 4.7. Список ребер має вигляд:
За списком ребер графа легко побудувати матрицю інцидентності, тому що кожне ребро цього списку відповідає стовпцю матриці, а номери вершин в кожному елементі списку - це номери елементів рядка матриці інцидентності, які дорівнюють 1.
Граф може бути представлений різними способами. Іноді нелегко зрозуміти, чи однакові графи, зображені різними кресленнями або різними матрицями. Графи, що відрізняються тільки нумерацією вершин, називаються ізоморфними. Перенумерація задається рядком нових номерів вершин, розташованих у вихідному порядку. Нова матриця суміжності виходить в результаті переміщення кожного елемента aij в рядок і стовпець, тобто в результаті перестановки () рядків і стовпців початкової матриці. Можна виконати всі можливі перестановки рядків і стовпців для того, щоб переконатися в неізоморфних графів, але це зажадає n. перестановок, що досить трудомістким.