# Graph Theory FUNdamentals

Graph Theory is the study of graphs that concerns the relationship between edges and vertices. In computer science, graphs are used to represent networks of communication, data organization, computational devices, and the flow of computation.

#### Applications of Graph Theory in Computer Science

1. Modeling Networks — Used to analyze network connections.
2. Social computing — Recommending mutual friends.

#### Other applications of Graph Theory

1. Science — Used in molecular structure, DNA structure of organisms.
2. Electrical Engineering — Used in the design of circuit connections.
3. Airplanes — Used in scheduling departures and arrivals

### Graph Theory Terminology

#### Point + Line

A point is an exact position on a plane surface, usually denoted by a letter.

A line is one-dimensional, and can be the connection between two points.

#### Vertex

A vertex, also called a node, is where multiple lines meet.

#### Edge

An edge is a line that connects two vertices.

#### Graph

A graph can be defined as G = (V, E), where V is the set of all vertices and E is the set of all edges.

#### Loop

A loop occurs when an edge is drawn from a vertex to itself.

### Types of Graphs

#### Simple Graph:

A graph with no loops and no parallel edges. The maximum number of edges possible in a simple graph with ’n’ vertices, is given by n^C2 where n^C2 = n(n–1)/2. To calculate the number of simple graphs possible with ’n’ vertices, 2^nc2 = 2^n(n-1)/2. For example, if n = 5, the maximum number of edges for that graph would be:

`n^C2 = n(n–1)/2   = 5(5–1)/2   = 20/2   = 10 edges--------------------------------------------------------------------2^nC2 = 2^n(n-1)/2   = 2^5(5-1)/2   = 2^10   = 1024`

#### Bipartite Graph:

A simple graph (G=(V,E)) with vertex partition where V= {V1, V2} and every edge of E connects a vertex in V1 to a vertex in V2.

#### Cyclic vs Acyclic Graphs:

Cyclic: Contains at least one cycle.

Acyclic: Contains no cycles.

#### Tree Graph:

Graphs which don’t contain cycles, which makes them acyclic. In computer science, trees are a data structures that connects vertices (nodes) in a parent-child relationship.

The edges of a tree are known as branches. Elements of trees are called their nodes. The nodes without child nodes are called leaf nodes.

#### Depth-first Search vs. Breadth-first Search

In a depth-first search, start at the root of the tree, and follow a branch until the vertex (node) you are looking for is reached, or until a leaf node is reached.

In a breadth-first search, start at the root of the tree, and find all the nodes that are one branch away from the root, then find all the nodes that are two branches away, and so on.

`       A      / \     B   C    /   / \   D   E   F`
`DFS approach -> A, B, D, C, E, F`
`BFS approach -> A, B, C, D, E, F`

#### Applications

Depth-first search is often used in simulations of games. Think of DFS as a game of chess, where your starting point leads to a series of moves played by your opponent, and vice versa.

Breadth-first search is mainly used to find the shortest path, that’s why it’s often used in GPS systems to find nearby locations. It’s even used in social networking sites to find people based on location or schools. Another example of BFS is the “six degrees of Kevin Bacon” game, where players try to find the shortest chain of actors/actresses who are connected to Kevin Bacon. You can play the game at https://oracleofbacon.org/.

Like what you read? Give Elizabeth Nicholson a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.