матрица на съседство

Разпространени начини за представяне свързаност на върхове в граф са: списък на ребрата; матрица на съседство, списък на съседи и др.

Матрицата на съседство е винаги квадратна - представя всеки връзка между всеки отделен връх и останалите.

Ако към връх няма нито едно ребро, то той е изолиран.

Ако в графа няма примки, по главния диагонал трябва да има само нули.

Ако графът е неориентиран, матрицата е симетрична спрямо главния си диагонал.

Ако не са дадени тегла на ребрата, то в матрицата на съседство има само 1 - има ребро, път между два върха или 0 - няма ребро.

Сложността за проверка наличие на ребро/път между два върха е винаги константна.

Броя 0-ли в матрицата за съседство дава информация доколко графа е разреден. Наличие само на 0-ли в даден ред от  матрицата показва, че съответния връх е изолиран, не е свързан с останалите.

Разновидност на матрицата на съседство  за претеглен граф:  вместо означаване наличие на ребро с 1 да се записва тегло на съответното ребро.

Друга разновидност е матрица на инцидентност за ориентиран граф. Отново редовете на матрицата дават информация за върховете, а стълбовете за ребрата. Стойността на елемента в позиция [ i ][ j ] е -1, ако реброто j излиза от върха i, стойността е 1 ако реброто j влиза във върха i, стойността е 0, ако нямо ребро към този връх.

Да се реализира проект, представящ вътрешнопредметни връзки в Информатика.

Тема на проекта: матрица на съседство.

Да се въвежда информация в матрица на съседство и да се извежда списък на съседите за същия граф.

В примерния проект се визуализира свързаност в ориентиран и неориентиран граф.

Брой на върховете се избира от списъчно поле, а вида на графа чрез радиобутони.

При ориентиран граф се въвежда тегло за съответното ребро чрез събитие On-Click върху съответния елемент от матрицата на съседство.

При неориентиран граф се въвежда информация за наличие на ребро чрез събитие On-Click върху съответната колона от матрицата на съседство. Автоматично се въвежда/изтрива наличие на ребро от симетрично разположения връх.. Чрез събитие On-Click върху съответния елемент от матрицата се визуализира връзката между двата върха.

Чрез команден бутон се извежда списък на съседите, заедно с информация за свързаност на графа и наличие на примки - за всеки отделен връх се описва дали има примка или е изолиран.

Разгледайте допълнителен материал за:свързаност в граф,  списък на съседство, цикъл в граф.