Cтраница 3
Значение 1 второго элемента строки А говорит о том, что из вершины А есть путь длины 1 в вершину В. Значение 1 второго элемента столбца С означает, что есть аналогичный путь от В к С. Следовательно, имеется путь длины 2 от вершины А к вершине С ( через вершину В) - этот факт и будет учтен в скалярном произведении благодаря слагаемому Хьв-Хвс, а значение всего скалярного произведения будет равно числу таких путей. [31]
Вспомогательной сети равен единице. Нетрудно заметить, что увеличивающая кратная цепь, найденная на каждой итерации главного цикла процедуры MAXPSA ( см. предыдущий раздел), имеет вид одиночной увеличивающей цепи. Теперь ясно, что во вспомогательной бескон-туриой сети длины / 2 поток идет вдоль максимального множества путей длины / 2 из s в t с попарно непересекающимися множествами промежуточных вершин. Этому множеству есте-ств нным образом соответствует максимальное множество чере - ДУКщихся цепей длины / с попарно непересекающимися множествами вершин ( под максимальным мы подразумеваем такое множество, которое нельзя увеличить на дополнительную чередующуюся цепь длины / и на множество вершин, не содер-жа. [32]
Говорят, что вершины х и у в графе смежны, если существует ребро, соединяющее их. Число ребер в пути ( в данном случае k - 1) называется длиной пути. На рис. 8.1 последовательность ( vt, u4), ( Vt, Vi), ( Vi, v2) - ( ve, y4, PI, У2) есть путь длины 3 между ц, и уа. Цикл - это путь, в котором первая и последняя вершины совпадают. Граф, который не содержит циклов, называется ациклическим. [33]
Матрица соединений С удобна для выражения многих полезных функций на графе. Например, / С задает выходные степени узлов, fC задает входные степени, /, С задает число соединений или дуг, Q С задает родственный граф с обратными направлениями дуг и С v QC задает родственный симметричный или неориентированный граф. С задает булев вектор, который представляет множество узлов, непосредственно достижимых из множества В. С задает соединения для путей длины два в графе CnCvCv. AC задает соединения для путей длины один или два. [34]
Матрица соединений С удобна для выражения многих полезных функций на графе. Например, / С задает выходные степени узлов, fC задает входные степени, /, С задает число соединений или дуг, Q С задает родственный граф с обратными направлениями дуг и С v QC задает родственный симметричный или неориентированный граф. С задает булев вектор, который представляет множество узлов, непосредственно достижимых из множества В. С задает соединения для путей длины два в графе CnCvCv. AC задает соединения для путей длины один или два. [35]
Математическая часть анализа не зависит от интересующих нас свойств или биологической активности. Если известно, что А и В обладают антималярийным действием, как в описанном здесь случае применения нашего метода, то упорядочивание отражает потенциальную антималярийную активность рассмотренных соединений. Если соединения А и В являются антиблокирующи-ми агентами, то полученное частичное упорядочивание будет указывать потенциальные антиблокирующие агенты. Как правило, при теоретико-графовом анализе свои собственные данные не образуются, а используются имеющиеся данные, для которых проводится поиск закономерностей, что дает возможность проследить их комбинаторное и топологическое происхождение. В основе нашего подхода лежит предположение, что: а) структурное сходство проявляется Р аналогичных свойствах и аналогичной биологической активности; б) выбранные инварианты графа pt ( путь длины /) довольно хорошо описывают структурное сходство. Понятие сходства в данном случае связывается с содержимым цепей в молекулярных графах, но ясно, что возможны и другие варианты выбора. [36]