`G = (:N, A, f:)`

• `N` - non-empty set of nodes
• `A` - set of arcs
• `f` - function that associates each arc with an unordered pair of endpoints

`G = (:{1,2,3,4,5,6}, {a,b,c,d,e}, {(a, 2-3), (b, 1-4), (c, 4-5), (d, 1-3), (e, 2-2)}:)`

(margin-left:50px)[http://192.168.1.110/wiki/attach/Discrete%20Math/figure1.png]

;Adjacent nodes:nodes that are connected by an arc. ;Loop:an arc that starts and ends with the same node. ;Loop free graph:graph with no loops. ;Isolated node:a node not adjacent to any other node. ;Degree:the number of arcs that end at a node. ;Parallel arcs:two arcs with the same endpoints. ;Simple:has no parallel arcs and no loops. ;Complete graph:all distinct nodes are adjacent (always connected). ;Path:a sequence of consecutive arcs in a graph. ;Path length:the number of arcs in the path. ;Connected graph:there is a path to every node in the graph. ;Cycle:a path exists from a node back to the same node such that no arc is used more than once. ;Acyclic:has no cycles. ;Tree:a graph that is connected and acyclic (including loops).
(margin-left:50px)[http://192.168.1.110/wiki/attach/Discrete%20Math/figure2.png]
* Node 1 is the starting node (or root node). * Node 1 is the parent node. * Nodes 2 and 3 are children of 1. * Nodes 4, 5, and 6 are children of 2. * Nodes 7 and 8 are children of 3.
* a and b are branches.
;Leaves:nodes with no children. ;Internal nodes:nodes that are non-leaves. ;Node depth:the length of the path from the root to the node. ;Height:the greatest depth.
A binary tree is a tree where each node has at most two children.
(margin-left:50px)[http://192.168.1.110/wiki/attach/Discrete%20Math/figure3.png]
A full binary tree is a binary tree where all internal nodes have two children and all leaves of the tree are at the same depth.
(margin-left:50px)[http://192.168.1.110/wiki/attach/Discrete%20Math/figure4.png]
Theorem - a tree with `n` nodes has `(n - 1)` arcs. !!Undirected Graphs

`G = (:N, A, f :)`

`G = (:{a, b, c}, {1, 2}, {(1, a-c), (2, c-b)}:)`

This graph is described as: the set of nodes, `a`, `b` and `c`; the set of arcs, `1` and `2`; arc `1` spans nodes `a` and `c`, arc `2` spans nodes `c` and `b`.

(margin-left:50px)[http://192.168.1.110/wiki/attach/Discrete%20Math/figure5.png] !!Directed Graphs

Directed graphs are identified by a function that associates an arc with an ordered pair of nodes.

`G = (:{a, b, c}, {1, 2}, {(1, (a, c)), (2, (c, b))}:)`

This graph is described as: the set of nodes, `a`, `b` and `c`; the set of arcs, `1` and `2`; arc `1` is directed from node `a` to node `c`, arc `2` is directed from node `c` to node `b`.

[{Image src='http://192.168.1.110/wiki/attach/Discrete%20Math/figure6.png' style='margin-left:50px' }]
;Initial node:the node from which an arc begins. ;Terminal node:the node where an arc ends. ;Adjacent node:in a directed graph, node `b` is adjacent to node `a` if there is an arc from node `a` to node `b`. ;Inverted arc:if there is an arc from node `a` to node `b`, an inverted arc would produce the opposite association from node `b` to node `a`.

[{Image src='http://192.168.1.110/wiki/attach/Discrete%20Math/figure7.png' style='margin-left:50px' }] Attributes of this graph: * Nodes `b` and `c` are adjacent to node `a`. Node `a` is not adjacent to nodes `b` and `c`. * Node `a` is adjacent only to node `d`. * Arc `5` is the only loop. * Arcs `2`, `3` and `4` form a cycle. * The degree of node `a` is 3; 2 arcs out, 1 arc in.
;Parallel arcs:arcs that have the same initial node and same terminal node.
[{Image src='http://192.168.1.110/wiki/attach/Discrete%20Math/figure8.png' style='margin-left:50px' }]
;Complete graph:all distinct nodes are adjacent.
[{Image src='http://192.168.1.110/wiki/attach/Discrete%20Math/figure9.png' style='margin-left:50px' }]
;Connected graph:a path exists from any node to any other node.
[{Image src='http://192.168.1.110/wiki/attach/Discrete%20Math/figure10.png' style='margin-left:50px' }] !!Adjacency Matrices

;Adjacency matrix:the number of arcs from one node to another node. An adjacency matrix describes which nodes in a graph are adjacent to which other nodes.

`G = (:{a, b, c}, {1, 2}, {(1, a-b), (2, b-c)}:)`
[{Image src='http://192.168.1.110/wiki/attach/Discrete%20Math/figure11.png' style='margin-left:50px' }] [{Image src='http://192.168.1.110/wiki/attach/Discrete%20Math/figure12.png' style='margin-left:50px' }]
Matrix dimensions are the number of rows by the number of columns.
E.g. 2 rows X 3 columns: `[(1, 0, 1),(0, 1, 1)]`
An adjacency matrix always has the same number of rows as columns.
[{Image src='http://192.168.1.110/wiki/attach/Discrete%20Math/figure13.png' style='margin-left:50px' }]
The main diagonal runs from the upper left to lower right corners of the matrix. The main diagonal will always have 0's in each position unless the graph has a loop. A loop in the graph will be indicated by a 1 on the main diagonal.
For a symmetric matrix, each side of the main diagonal is a mirror image of the other.
An undirected graph always has a symmetric adjacency matrix.

!!Matrix Multiplication

;Square Matrix:a matrix with the same number of rows and columns. ;Zero Matrix:a matrix with all zeros.
`[(0, 0, 0),(0, 0, 0)]`
;Identity Matrix:a matrix with all 1'a along the main diagonal with 0's in all other positions. An identity matrix must be square.
Identity matrix: `I = [(1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1)] 4 xx 4`

Not identity matrix: `[(1, 0, 0, 0), (0, 1, 0, 0)] 2 xx 4`

`I * A = A`

Matrix multiplication is NOT commutative. Order does make a difference.
`A * B != B * A` !Scalar multiplication of matrices `2 * [(a_(11), a_(12)), (a_(21), a_(22))] = [(2 * a_(11), 2 * a_(12)), (2 * a_(21), 2 * a_(22))]` !Product of matrices `A * B = C`
The number of columns in `A` must be the same as the number of rows in `B` to multiply.
` A  *  B  =  C`
`2xx3  3xx4   2xx4`

amath [(a_(11), a_(12)), (a_(21), a_(22))] * [(b_(11), b_(12)), (b_(21), b_(22))] = [(a_(11) * b_(11) + a_(12) * b_(21), a_(11) * b_(12) + a_(12) * b_(22)), (a_(21) * b_(11) + a_(22) * b_(21), a_(21) * b_(12) + a_(22) * b_(22))] = [(c_(11), c_(12)), (c_(21), c_(22))] endamath

Adjacency Matrices (cont.)

Given the following graph:
`G = (:{a, b, c}, {1, 2}, {(1, a-b), (2, b-c)}:)`
[{Image src='http://192.168.1.110/wiki/attach/Discrete%20Math/figure11.png' style='margin-left:50px' }] [{Image src='http://192.168.1.110/wiki/attach/Discrete%20Math/figure14.png'}]

`A * A = A^2 = [(0, 1, 0), (1, 0, 1), (0, 1, 0)] * [(0, 1, 0), (1, 0, 1), (0, 1, 0)] = [(0*0+1*1+0*0, 0*1+1*0+0*1, 0*0+1*1+0*0),(1*0+0*1+1*0, 1*1+0*0+1*1, 1*0+0*1+1*0), (0*0+1*1+0*0, 0*1+1*0+0*1, 0*0+1*1+0*0)] = [(1, 0, 1), (0, 2, 0), (1, 0, 1)]`

[{Image src='http://192.168.1.110/wiki/attach/Discrete%20Math/figure15.png'}]

`A` represents the number of paths of length 1. * There is one path from node `a` to node `b`. * Likewise, there is one path from node `b` to node `a`. * There is one path from node `b` to node `c`. * There is one path from node `c` to node `b`.
`A^2` represents the number of paths of length 2. * There is one path of length 2 from node `a` to node `a`. The path traverses from node `a` to node `b` then back to node `a`. * There is one path of length 2 from node `c` to node `c`. * There are two paths of length 2 from node `b` to node `b`. The first traverses from node `b` to node `a` then back to node `b`. The second traverses from node `b` to node `c` then back to node `b`. * There is one path of length 2 from node `a` to node `c`. The path traverses from node `a` to node `b` then continues on to node `c`. * There is one path of length 2 from node `c` to node `a`.
`A^n` represents the number of paths of length `n` between any two nodes.

In determining the value of `n`, consider the number of distinct nodes - 1 (not including isolated nodes).
`R = A + A^2 + A^3 + … + A^n`
`R` - The number of paths `⇐` length `n`