Способы задания графов:
<{a,b,c,d},{u,v,w,x}; {(u,a),(u,b),(v,b),(v,c),(w,c),(w,a),(x,c), (x,d)}>.
Так как мы рассматриваем только простые графы, граф нам проще определять как модель, носителем которой является множество вершин, а отношение – бинарное отношение смежности вершин.
Тогда данный граф запишется как <{a,b,c,d};
{(a,b), (b,a),(b,c),(c,b),(a,c),(c,a),(c,d),(d,c)}>. В таком представлении ребру соответствуют две пары вершин (v1,v2) и (v2,v1), инцидентных данному ребру.
Чтобы задать такое представление, достаточно для каждого ребра указать двухэлементное множество вершин – его мы и будем отождествлять с ребром. Для данного графа рёбра задаются множеством {{a,b},{b,c},{a,c},{c,d}} и граф мы будем записывать как пару (V,E), где V – множество вершин, а E – множество рёбер.
Это квадратная матрица порядка п (п – число вершин), в которой нули стоят по главной диагонали (если в графе нет петель, а если петли есть в вершине k (и число этих петель равно р), то на главной диагонали в строчке с номером k стоит число р). Если вершина i связана с вершиной j одним ребром, то элемент матрицы смежности aij равен 1, если эти вершины связаны s ребрами, то аij= s. Аналогичным образом строятся матрицы смежности для орграфов и для мультиграфов.
Это матрица размера nхm, где n – число вершин, а m – число ребер графа, при этом ее элементы kij равны 1, если вершина с номером i является для ребра с номером j начальной или конечной (если ребро неориентировано) и начальной для ориентированных ребер. Заметим, что матрица инциденций сравнительно редко используется, так как в современных условиях (где число ребер часто очень велико) она имеет слишком большое число столбцов.
Матрицей инцидентности (инциденций) ориентированного графа называется матрица 
, для которой 
, если вершина 
является началом дуги 
, ,-1 если является концом дуги , в остальных случаях 0.
