Шпори в дискретната математика2 - страница 2
Броят на свързаните компоненти на графа G се означава с c(G). Графиката G е свързана тогава и само ако c(G)=1. Ако c(G)>1, тогава G е несвързана графика. Граф, състоящ се само от изолирани върхове, се нарича напълно несвързан.
19.Силна свързаност. Два върха u, v в диграф G са свързани чрез двупосочна релация на достижимост, ако има маршрут от u към v и от v към u. Орграф, в който всеки два върха са двустранно достижими, се нарича силно свързан. Тривиален граф, състоящ се от изолиран връх, по дефиниция се счита за силно свързан.
Двупосочната релация на достижимост на върха е релация на еквивалентност. Силно свързан компонент на диграф G е неговият силно свързан подграф, който не е правилен подграф на който и да е друг силно свързан подграф на диграфа G. Класовете за еквивалентност на двустранна достижимост са разделяне на набора от върхове на диграфа G на подмножества от върхове, включени в един силно свързан компонент. За да се конструира силно свързана компонента, е достатъчно да се вземе един клас на еквивалентност и да се прехвърлят връзки (дъги) от орграфа G към множеството от върховете му.Броят на силно свързаните компоненти на орграфа G да се означи с k(G). Орграф G е силно свързан тогава и само ако k(G)=1. Ако k(G)> 1, тогава G не е силно свързан орграф.
Еднопосочна свързаност. Орграф G се нарича еднопосочно свързан, ако за всеки върх u, v има маршрут в поне една посока.
Ако един диграф е силно свързан, тогава той също ще бъде едностранно свързан.
Слаба връзка. Псевдограф, свързан с диграф G=(V,E) е псевдограф G1=(V1,E1), в който E1 се получава от E чрез замяна на всички дъги(подредени двойки) към ръбове (неподредени двойки).
Диграф G=(V,E) се нарича слабо свързан, ако неориентираният граф, свързан с него, е свързан.
20. Нека G=(V,E) е граф (диграф) с n върха и q ребра.Ако A=A(G) е матрицата на съседство на графа (диграф) G, тогава aij елемент на матрицата Аk е броят на маршрутите от vi до vj с дължина k.В n върховия граф (диграф) G, тогава и само ако има маршрут от vi до vj (i∫j), когато (i,j)-ият елемент на матрицата не е равен на нула.
В n върхова графа (диграф) G тогава и само ако има цикъл; съдържащ върха ai, когато (i,i)-ият елемент на матрицата не е равен на нула. Нека формираме матрица C=(cij) от ред n от матрица B съгласно следното правило: Cij=1 ако bij≠0; Cij=0, ако bij=0, където bij са елементи от матрица B.
Матрица C се нарича матрица на свързаност, ако G е неориентиран граф, и матрица на достижимост, ако G е диграф. В графика G има маршрут от vi до vj, когато cij=1. Матрицата C съдържа информация за съществуването на връзки между различни елементи на графа чрез маршрути. Ако G е свързан неориентиран граф, тогава всички елементи на матрицата на свързаност C са равни на единица. В общия случай матрицата на свързване на неориентиран граф е матрицата на релация на еквивалентност, съответстваща на разделянето на набора от върхове на графа на свързани компоненти.