# 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**

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

#### Other applications of Graph Theory

- Science — Used in molecular structure, DNA structure of organisms.
- Electrical Engineering — Used in the design of circuit connections.
- 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/.