Graph Theory_FINAL (1)

Graph Theory

Applications

• Road and Rail Networks

• Computer Chips

• Supply Chains

• Friendships

• Neural Connections

• The Internet

Graph Definition

• Graph: Consists of points called vertices connected by edges.

• Representation: G = (V, E) where V = set of vertices, E = set of edges.

Edge Types

Directed Edges

• Ordered pair: (u, v) directs from vertex u to v.

Undirected Edges

• Unordered pair: {u, v}.

Other Edge Types

• Loop: Edge connecting a vertex to itself (e.g., {u, u}).

• Multiple Edges: Two or more edges connecting the same pair of vertices.

Graph Types

Simple Graph

• Consists of distinct vertices and no multiple edges or loops.

• Representation: G(V, E).

• Example: V = {u, v, w}, E = {{u, v}, {v, w}, {u, w}}.

Multigraph

• Can have multiple edges and loops between the same vertices.

• Example: Graph with edges joining B and C multiple times.

Directed Graph

• G(V, E) where edges are ordered pairs.

Graph Properties

Undirected Graphs

• Adjacent Vertices: If {u, v} is an edge.

• Degree of Vertex (deg(v)): Number of edges connected to vertex v.

  • Isolated: deg(v) = 0

  • Pendant: deg(v) = 1

Directed Graphs

• In-Degree: Number of edges leading to vertex.

• Out-Degree: Number of edges leading from vertex.

Theorems

Handshaking Theorem

• 2e = sum of degrees of all vertices.

Odd Degree Vertices

• Undirected graphs have an even number of odd degree vertices.

Euler Graph

• An Eulerian path uses each edge exactly once.

• An Eulerian cycle uses each edge exactly once and returns to starting vertex.

Hamiltonian Graph

• A Hamiltonian path visits each vertex exactly once.

• A Hamiltonian cycle is a cycle visiting each vertex exactly once.

Planar Graphs

• Can be drawn without overlapping edges.

• Example: VLSI design, circuit design.

Graph Representation Techniques

• Incidence Matrix: Useful for edges over vertices.

• Adjacency Matrix/List: Useful for vertices over edges.

• Edge List: Each element represents an edge connecting nodes.

Traversal Algorithms

Depth-First Search (DFS)

• Starts from a node and explores as far as possible along each branch.

• Implemented using a stack structure.

Breadth-First Search (BFS)

• Visits all immediate neighbors before moving to the next level.

• Implemented using a queue structure.