Определение
Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента aijравно числу рёбер из i-й вершины графа в j-ю вершину.
Иногда, особенно в случае неориентированного графа, петля (ребро из i-й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента aii в этом случае равно удвоенному числу петель вокруг i-й вершины.
Матрица смежности простого графа (не содержащего петель и кратных ребер) является бинарной матрицей и содержит нули на главной диагонали.
Ниже приведён пример неориентированного графа и соответствующей ему матрицы смежности A. Этот граф содержит петлю вокруг вершины 1, так что, в зависимости от конкретных приложений, элемент a11 может считаться равным либо единице (как показано ниже), либо 0.
-
Граф
Матрица смежности
Матрица смежности полного графа Kn содержит единицы во всех своих элементах, кроме главной диагонали, на которой расположены нули.
Матрица смежности пустого графа, не содержащего ни одного ребра, состоит из одних нулей.
Билет 12 Алгоритмы Маркова
Суть этих самых алгоритмов Маркова в следующем. Задача для алгоритмов Маркова ставится в виде: найти алгоритм (написать программу) переводящую любую строку S (заданную на некотором алфавите (т.е. наборе символов, которые могут в нее входить)) из некоторого допустимого множества входных строк в строку f(S). Т.е., построить программу - преобразователь строк, выполняющую некое преобразование. Например: перевести все буквы в строке в верхний регистр, инвертировать регистр, перевернуть строку задом-наперед (reverse), и даже такую задачу: из строкового представления десятичного числа получить строковое представление числа на единицу больше (или в 2 раза больше).
Билет 8. Понятия: «функция», «инъекция», «сюръекция», «биекция». Примеры.
Отображение называется сюръективным (или сюръекцией, или отображением на ), если каждый элемент множества является образом хотя бы одного элемента множества , то есть . Для случаячисловых функций это выражается как «функция, принимающая все возможные значения».
Примеры
— сюръективно.
— сюръективно.
— не является сюръективным (например, не существует такого , что ).
Биекция — это отображение, которое является одновременно и сюръективным, и инъективным. При биективном отображении каждому элементу одного множества соответствует ровно один элемент другого множества, при этом, определено обратное отображение, которое обладает тем же свойством. Поэтому биективное отображение называют ещё взаимно-однозначным отображением (соответствием), одно-однозначным отображением.
Примеры
Тождественное отображение на множестве биективно.
— биективные функции из в себя. Вообще, любой моном одной переменной нечетной степени является биекцией из в себя.
— биективная функция из в .
не является биективной функцией, если считать её определённой на всём .
Отображение называется инъекцией, если для любых элементов x1, x2 X, для которых f(x1) = f(x2) следует, что x1 = x2. (рис. 7)