Определение

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента a_ij равно числу рёбер из i-й вершины графа в j-ю вершину.

Иногда, особенно в случае неориентированного графа, петля (ребро из i-й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента a_ii в этом случае равно удвоенному числу петель вокруг i-й вершины.

Матрица смежности простого графа (не содержащего петель и кратных ребер) является бинарной матрицей и содержит нули на главной диагонали.

Примеры

• Ниже приведён пример неориентированного графа и соответствующей ему матрицы смежности A. Этот граф содержит петлю вокруг вершины 1, так что, в зависимости от конкретных приложений, элемент a₁₁ может считаться равным либо единице (как показано ниже), либо 0.

Граф	Матрица смежности

• Матрица смежности полного графа K_n содержит единицы во всех своих элементах, кроме главной диагонали, на которой расположены нули.

• Матрица смежности пустого графа, не содержащего ни одного ребра, состоит из одних нулей.

13 Понятие равномощности множеств. Примеры. Равномощность множеств

Рассмотрим два множества A и B.

Отображение f из A в B (обозначается f: A  B) – это правило, которое каждому элементу множества A ставит в соответствие элемент множества B, причем ровно один. (При этом не запрещается двум элементам множества A ставить в соответствие один и тот же элемент множества B, рис. 1, а .)

а ) б ) Рис. 1

Отображение f называется взаимно однозначным , если каждый элемент множества B поставлен в соответствие ровно одному элементу множества A (рис. 1, б ).

Множества A и B называются равномощными , если существует взаимно однозначное отображение f: A  B. Понимать это можно так: множества равномощны, если в них одинаковое количество элементов.

Например, множества {0,1,2} и {лошадь,корова,телевизор} равномощны, а множества {0,1,2} и {лошадь,корова} неравномощны^*7. А равномощны ли множества  и {}? Неравномощны: в множестве  нет ни одного элемента, а в множестве {} есть один элемент – пустое множество (множество {} – это коробка, в которой лежит пустое множество, а пустое множество – это коробка, в которой ничего не лежит).

14 Теорема Кантора-Шрёдера-Бернштейна (без доказательства). Примеры применений этой теоремы. Теорема Цермело (без доказательства).

Теорема Кантора — Берштейна (в англ. литературе Теорема Кантора — Бернштейна — Шрёдера или Теорема Шрёдера — Бернштейна) утверждает, что если между двумя множествами существуют инъекции, то они равномощны.

Пусть даны два множества A и B. Тогда если существуют инъективные отображения и , то существует и биекция , то есть множества A и B равномощны.

Теорема Цермело Любое множество может быть вполне упорядочено