Non-formal Definition of Graphs in Mathematics

Imagine a world where a 'graph' is not just a line graph in a coordinate system, but a collection of nodes and edges connecting them. This is the essence of graph theory, a branch of discrete mathematics.

Nodes and Connections

A graph in graph theory is a set of entities known as 'nodes' or 'vertices' along with connections between some or all of these nodes. These connections are referred to as 'edges' or 'links'. The edges may or may not have 'weights', where higher weights indicate a stronger connection. In simpler terms, a graph is essentially a network.

Examples and Visual Representation

Let's consider an example of an air travel map. In this map, each airport is a node, and flight schedules between airports are the edges. Here's a simplified version of such a graph:

1: NYC 2: HOU 3: LAX 4: SFO 5: ORD 6: SEA

In this graph, the numbers represent different airports. This is easier to understand than trying to explain the connections through plain English. Visual representation helps in comprehending the complex web of connections more effectively.

Types of Graphs

Graphs can be classified into several types based on the nature of their edges and nodes.

Undirected Graphs: In an undirected graph, an edge has no direction. For example, in an air travel map, an edge from node 1 to node 2 (representing flights between NYC and HOU) is the same as an edge from node 2 to node 1. Directed Graphs: In a directed graph, an edge has a direction. For instance, in a family tree, an arrow from a parent to a child is different from an arrow from a child to a parent, indicating the flow of relationship.

Some graphs, like the family tree, are directed by nature. Others, like the air travel map, can be either directed or undirected depending on the context. Directed graphs are also known as DAGs (Directed Acyclic Graphs) if they do not have any cycles.

Representation of Graphs

Graphs can be represented in different forms to serve various purposes.

Graph Diagrams: Visual representation where nodes are points and edges are lines or arcs connecting them. This is great for visualizing connections and paths. Algebraic Representation: Representing a graph using sets and ordered pairs. For the rock-paper-scissors game, the graph can be represented as a pair of sets: {rock, paper, scissors} and {rock scissors, scissors paper, paper rock}.

Whether you represent a graph using a diagram or algebraic notation, the underlying structure and properties of the graph remain the same, making it easier to prove theorems and model real-world scenarios.

Conclusion

In summary, a graph in graph theory is a set of nodes and edges connecting them. Whether you're mapping air travel routes, plotting family trees, or modeling network connections, the core concept of graph theory remains constant. The flexibility in representing graphs allows mathematicians and computer scientists to analyze and manipulate these structures effectively.