Graphs (AS)

Graphs (AS)

Introduction to Graphs

• Graphs are systems with nodes, also called points or vertices, connecting lines or edges.
• Graphs help model different situations in order to solve complex real-world problems.

Types of Graphs

• Undirected graphs: Edges do not have a direction, typically represented by lines.
• Directed graphs (digraphs): Edges do have a direction, indicated by arrows.
• Weighted graphs: Edges are assigned a weight, often representing costs, distances, etc.
• Trees: Special type of graph, with no cycles and all nodes connected.

Key Graph Terminology

• Order of a graph: The number of vertices in the graph.
• Size of a graph: The number of edges in the graph.
• Degree of a vertex: The number of edges connected to a vertex.
• Loop: An edge that connects a vertex to itself.
• Cycle: A closed path, i.e., starts and ends at the same vertex without retracing any edge.
• Complete graph: A graph in which every pair of distinct vertices is connected by a unique edge.

Graph Travelling and Traversing

• Walk: A sequence of vertices and edges connecting two vertices.
• Path: A walk in which no vertex or edge is repeated.
• Eulerian trail/circuit: A trail/circuit that uses every edge in the graph exactly once.
• Hamiltonian path/circuit: A path/circuit that visits every vertex in the graph exactly once.

Graph Isomorphism

• Isomorphic graphs are essentially the same graph which can appear different due to different vertex arrangements.
• Isomorphisms preserve degrees, distance, adjacency and connectivity, among other properties.

Planar Graphs

• A planar graph can be drawn on a plane without any crossing edges.
• Faces refer to the regions bounded by the edges in a planar graph.
• Euler’s formula relates the number of vertices, edges, and faces in a planar graph : vertices + faces = edges + 2.

Matrices and Graphs

• Adjacency Matrix: A square matrix used to represent a finite graph.
• Incidence Matrix: A Matrix that shows the relationship between two sets of entities.