# Graphs

A graph is a collections of** vertices/nodes** and **edges(arcs)**.It is like a tree structure with a difference that it** does not** have any** parent-child** relationship between nodes.Instead,any complex relationships are possible between the nodes.A Graph **G**(Fig 1) is defined as an ordered set **(V,E)**,where **V(G)** is the set of vertices and **E(G)** represents the edges that connect the vertices together.

Fig 2 shows a graph with V(G) = {A,B,C,D,E,F}

E(G) = {(A,B),(A,C),(B,D),(C,D),(C,F),(D,E)}

There are 6 nodes and 6 edges in this Graph.

## Terms associated with Graph

**Adjacent Nodes**- For every edge,**E = (U, V)**that connects nodes**U**and**V;**the nodes U and V are the end-points and are said to be the adjacent nodes.In Fig 2,**A and B**are**adjacent nodes.****Degree**- Degree of a node a is the total**number of edges**associated with the particular**node**.For e.g. ,degree of vertex A in Fig 2 is 2.**Path**- The**route/way**followed by**edges**from**one node**to**another node**.**Cycle**- A**closed simple path**with**length 3**or more is known as cycle.For e.g. P = {A,B,D,E,F,D} forms a cycle in Fig 3.**Multiple edges**-**Distinct edges**which connect the**same end points**/vertex are known as multiple edges.**E = (A,C)**and**E' = (D,C)**are**multiple edges**in Fig 2.**Loop**- An edge that has**identical end points**is called as Loop.**P = {A,B,D,C,A}**forms a**loop**in**Fig 2**.**Size of Graph**- It is the**total**number of**edges**in the graph**.Size**of graph in Fig 2 is**6**.

## Types of Graphs

### Directed Graph

In a **directed graph**,edges have an **orientation** and form an** ordered pair** (Fig 3). If there is an edge from A to B, then there is a path from A to B but not from B to A. The edge (A, B) is said to initiate from node A (also known as initial node) and terminate at node B (terminal node).Fig 3 is a directed graph with directed edges {(A,B),(B,D),(D,E),(E,F),(F,D)}

### Undirected Graph

A graph is called as **undirected** if the edges **do not** have any** orientation**.The **edge** can be** traversed** from **one point** to **another** and vice versa.Traversal can be done from A to B and B to A in Fig 4 and same is applicable for other nodes also.

### Regular Graph

A **regular graph** is a graph where each **vertex **Â has the **same number** of **neighbors**, i.e., every vertex has the **same degree** . In Fig 5.degree of every vertex is 2.

### Connected Graph

A graph is said to be** connected** if there is **no isolated node** and there exists a **path** between any of the **two nodes** i.e there will be** at least** one edge **emerging** from any of the vertices in graph(Fig 6).

### Complete Graph

A graph G is said to be a **complete**, if there is **always** a **path **from **one node** to** another **i.e if all the nodes are fully connected(Fig 7).

### Weighted Graph

A graph is said to be **weighted** if every edge has** some data/value ** associated with it.It is denoted by **w(e)** and is a** positive value** referring to the cost of traversing the edge.Weight of the graph as shown in Fig 8 , w(e) is** 29**.Cost of traversing edge A to B is 2,B to C is 5,C to D is 6,D to E is 9,E to A is 7.

### Multi-Graph

A graph in which **vertex ** have **multiple edges ** and /or ** loops** is called a multi-graph(Fig 9).

## Comments

So empty here ... leave a comment!