Graph Theory
Graph Theory is a field of mathematics that focuses on studying graphs (also known as networks) to solve problems in many areas, including:
- Setting examination timetables
- Colouring maps
- Modelling chemical compounds
- Designing circuit boards
- Building computer, communication, or transportation networks
- Determining optimal paths
In graph theory, graphs are made up of vertices (also called nodes) and edges (the connections). These graphs help show relationships between various entities.
Networks, Nodes, Vertices, and Edges
- Graphs (or networks) consist of a collection of points (nodes/vertices) connected by lines (edges)
- Nodes (or vertices) are the points in the network that represent different objects, such as cities, computers, or people
- Edges are the lines linking the nodes, showing relationships or connections, like roads, wires, or friendships
Neighbours
- Two vertices are considered neighbours if they are directly connected by an edge
- The degree of a vertex is the number of edges that are linked to it
- Example: If a city is connected to three other cities by roads, its degree would be 3
Categorizing Networks
Connected vs. Disconnected Networks
- A connected network has at least one path between every pair of vertices
- A disconnected network has at least one vertex that cannot be reached from others
Complete Networks
- A complete network has an edge between every pair of vertices
Traceable Networks
- A network is traceable if it is possible to travel along all edges exactly once
- A network is NOT traceable if it is impossible to travel along all edges exactly once
- Euler’s Rule: A network is traceable if all vertices have even degrees or exactly two vertices have odd degrees
Planar vs. Non-Planar Networks
- A planar network can be drawn so that no edges cross except at vertices
- A
non-planar network cannot be redrawn without edges crossing
These concepts help solve real-world problems like city planning, scheduling, and network design.
The degree of a vertex is the number of edges that are connected to it. It is determined by counting how many edges meet at that vertex. For example, if a city is connected to three other cities by roads, the degree of that vertex (city) would be 3.
A disconnected network has at least one vertex that cannot be reached from other vertices, meaning some vertices are isolated from others in the network.