Graphs for the Baccalaureate

Undirected graphs

A Graph is composed of a set of vertices (nodes) and a set of edges G=(V, E).
- Vertices are the fundamental units of the graph. Sometimes, vertices are also known as vertex or nodes.
- Each edge has two ends, which are vertices to which it is attached.

The unordered pair formed by vertices x and y is denoted (x,y); the vertices x and y are called the extremities of the edge (x,y).
A neighbor of a vertex x is any vertex y, with the property that there exists the edge (x,y).

Adjacency
If two vertices x and y are endpoints of the same edge, they are adjacent.

Incidence
Two edges are incident if they have a common endpoint. A vertex is incident to an edge if the vertex is an extremity of that edge.

Exemple (Fig. 1):
G=(V,E)
|V|=7
E={(1,2), (1,4), (1,7), (2,3), (3,6), (3,7), (6,7), (6,1)}
The edge (3,6) is incident to nodes 3 and 6.
Nodes 3 and 6 are called adjacent nodes.
Vertex 3 is incident to edge (3,6).

Degree of a vertex
The number of edges incident to a vertex is called the degree of that vertex in the graph. The degree of the vertex x is denoted by d(x).
For example, for the undirected graph illustrated in Fig. 1:
d(1)=4, d(2)=2, d(3)=3, d(4)=1, d(5)=0, d(6)=3, d(7)=3

It is called an isolated node, the node whose degree equals 0.
It is called a terminal node, the node whose degree equals 1.
For example, in the undirected graph in Fig. 1, node 5 is isolated and node 4 is terminal.

Observation:
The sum of the degrees of the vertices of an undirected graph is equal to twice the number of edges in the graph.

Chain, cycle
A sequence of nodes with the property that the first node is different from the last and there is an edge between any 2 successive nodes in the chain is called a chain. The first and last nodes are called the extremities of the chain .

- A chain is called elementary if it does not contain the same node more than once.
Eg. from Fig. 1: [1,7,6,3]
- A chain is simple if it does not contain the same edge more than once, but can pass through the same node more than once.
Eg. from Fig. 1: [1,7,6,1,2,3]
- A chain is called compound if it passes through one or more edges more than once.
Eg. from Fig. 1: [1,7,6,1,6,3]
The number k-1 is called the length of the chain and is the number of edges it consists of(k=the number of nodes).

A sequence of nodes with the property that the last node is the same as the first and there is an edge between any 2 successive nodes in the chain is called a cycle. If all vertices are distinct except the first and last, it is called an elementary cycle.
Eg. from Fig. 1: [1,2,3,7,1]
The length of a cycle is equal to the number of edges in the cycle, the minimum length being 3.

Graphs associated with a given one
- A partial graph of a graph G is obtained by removing edges from the graph G.
- A subgraph of a graph G is obtained by removing vertices from the graph G, together with all edges incident to them.

Hamiltonian Graph
- The graph containing a Hamiltonian cycle is called a Hamiltonian graph.
- It is called a Hamiltonian cycle, the elementary cycle that passes through all the nodes of the graph.
The sufficient condition for a graph to be Hamiltonian is that the degree of a node is greater than or equal to half the number of nodes.
Eg: The graph illustrated in figure 2 is Hamiltonian.
Hamiltonian cycles: [1,2,3,4,5,6,7,1], [1,2,4,3,5,6,7,1]

Eulerian Graph
- The graph containing an Eulerian cycle is called an Eulerian graph.
- It is called an Eulerian cycle, the simple cycle that traverses all edges of the graph.
The necessary condition for a graph to be Eulerian is that the degree of each node is even and there are no isolated nodes.
Eg: The graph illustrated in figure 3 is Eulerian.
Eulerian cycle: [1,3,4,5,6,3,2,1]

Null Graph
If there are several vertices but no edges connect them, a graph G= (V, E) is a null graph.

Regular Graph
A graph whose vertices have the same degree is called a regular graph.

Complete Graph
An undirected graph is called complete if any two vertices in the graph are adjacent (the graph in which the edge (x,y) exists, whatever x≠y in the set of nodes).
Eg: The unoriented complete graphs with n=3, 4, 5 nodes.

Connectedness
- It is called a connected graph, the graph in which there is at least one chain between any two of its nodes (if it admits only one connected component).
- It is called connected component, the maximal subgraph in relation to the connectedness property.
- A graph is biconex if it is connected and for any vertex removed, the generated subgraph retains its connectedness property.

Eg:
The illustrated graph in Fig. 4 is connected.
The illustrated graph in Fig. 5 it consists of three connected components:
{1,2,3,5,7,10}
{4,8,9}
{6}

Bipartite Graph
A graph G=(V, E) is called a bipartite graph if there are two nonempty sets A and B such that V=A∪B, A∩B=∅ and any edge of G has one endpoint in A and the other in B .The sets A and B form a partition of E.

Ways of representing undirected graphs

1. Adjacency Matrix

The adjacency matrix, associated with the graph G=(V, E), is a square matrix of order n, with the elements defined as follows: a[i][j]=1, if [i,j] belongs to E or a[i][j]=0 , if [i,j] does not belong to E.
Observations:
- the adjacency matrix is symmetric about the main diagonal;
- the elements on the main diagonal are 0;
- the degree of a vertex x is equal to the number of elements 1 on the line (or column) x;
- the sum of all elements in the adjacency matrix of an undirected graph is equal to twice the number of edges in the graph.

2. Adjacency List

For an undirected graph with G=(V,E), the number of vertices n will be memorized and then, for each vertex x, the list of vertices adjacent to x, i.e. of vertices y with the property that the edge [x,y] exists.

3. List of edges

The edge list of an undirected graph is a set containing all the edges in the graph.
E = {(1,2), (1,3), (1,4), (3,4), (2,3)}

Trees

A tree is an undirected connected acyclic graph, where one of the nodes is designated as the root.
An undirected acyclic and disconnected graph is called a forest.
Nodes can also be placed on levels, starting with the root, which is placed on the first level. The root is the node that generates the tree layout.
In a tree, m=n-1, where n represents the number of nodes in the graph and m represents the number of edges.

- A node A is a descendant of a node B if it is located at a higher level than B and there is a chain connecting them that does not pass through the root.
- A node A is the son / direct descendant of a node B, if it is located immediately on the next level of node B and there is an edge between A and B.
- A node A is the ascendant of a node B, if it is located at a lower level than B and there is a chain connecting them that does not pass through the root.
- A node A is the parent of a node B, if it is located on a level immediately above node B and there is an edge between A and B.
- Two nodes are siblings if they have the same parent.
- A node is leaf if it has no children.

Tree height is the length of the longest chain from the root to the leaves.

Eg:
In the illustrated tree in Fig. 6 (with the height = 3):
5 — root;
4, 3, 10, 6, 9 — leafs;
2 — parent for 3 and 10;
3, 10 — sons of 2; siblings; direct descendants of 2;
2 — direct ascendant of 10;
2, 5 ascendants of 10;
8, 9, 6 — descendants of 7.

Observations:
- To obtain the maximum height of a tree, we choose as the maximum root any node at the extremity of the longest chain.
- To obtain the minimum height of a tree, the node(s) in the middle of the longest chain can be chosen as the root.

Methods of representing trees in memory

1. Adjacency Matrix

For the illustrated tree in Fig. 6, the adjacency matrix can be represented:

2. Vector of parents (Representation by ascending references)

For each node, information about direct descendants is stored. We will obtain a vector of parents, in which:
- t[r] = 0, where r is the root of the tree;
- t[k] = parent of node k.
For the illustrated tree in Fig. 6, vectorul de tați poate fi reprezentat astfel:

Properties:
- There is only one value of 0, corresponding to the root;
- Nodes that do not appear are leaves;
- The degree of any node is equal to the number of its occurrences + 1 (except the root, where the degree is equal to the number of occurrences).

Binary Trees

It is called a binary tree, the tree in which any node has at most two children. They are called left son (left descendant) and right son.
Internal node represents any node except leaves.

Eg. in Fig. 7:
6 — root;
the root has two direct descendents (sons) — 4 is a left descendent of 6, and 1 is its right descendent;
node 4 has only one descendent, node 5 — which is the left descendent of node 4;
similarly, 9 — right descendent of 5;
nodes 5, 6 and 7 — terminal nodes (leafs).

It is called balanced binary tree, the binary tree in which all leaves are found on at most 2 successive levels.
An example of a balanced binary tree is illustrated in Fig. 8.

It is called a complete binary tree, the tree that has all leaves on the same level and all internal nodes have both children.
An example of a complete binary tree is illustrated in Fig. 9.
The number of nodes of a complete binary tree with k levels = 2^k-1.

It is called a full binary tree, the binary tree in which each level k∈{0, 1, 2, ..., h}, where h is the height of the tree, contains 2^k nodes.
An example of a full binary tree is illustrated in Fig. 10.
A full binary tree with k terminal nodes has 2k-1 nodes.

It is called a strict binary tree, the binary tree in which every node, except the terminal nodes, has exactly 2 descendants.
An example of a strict binary tree is illustrated in Fig. 11.

Observations:
- To result in a binary tree, we can choose any node as the root, which has degree less than 3.
- If there is a node in the graph that has degree greater than 3, then it cannot be converted into a binary tree.
- We can consider that each node of the binary tree subordinates a left binary subtree and a right binary subtree.

Undirected graphs

Trees

Binary Trees

Information