Mathematics - Discrete Mathematics - Graphs

about 2 years ago

Introduction

Hey it's a me again @drifter1!

Today we continue with Mathematics, and more specifically the branch of "Discrete Mathematics", in order to get into Graphs.

So, without further ado, let's get straight into it!

Graph Theory

Graph Theory is the branch of mathematics concerned with the study of objects known as graphs. Graphs consist of vertices (or nodes) which are connected by edges.

Many problems can be represented and solved using them, and thus Graph theory finds applications in not only mathematics, but also physics and computer science as well.

Graphs

A graph is defined as G = (V, E), where:

V is the set of vertices or points or nodes
E is the set of ordered pairs of distinct vertices known as edges

For example:

Let's get through some terminology now...

Vertices

Two distinct vertices u and v of a graph are adjacent if an edge e = (u, v) connects them. The set of all vertices adjacent to a given vertex v is defined as N(v) and known as the neighborhood of v. The number of edges that are incident to a given vertex v is defined as the degree of that vertex and denoted as deg(v).

Vertices of degree one are called pendant. In a similar manner, vertices with odd degree are odd, and vertices with even degree are even.

In the example graph mentioned previously each vertex is of degree 2, and so all vertices are of even degree.

Types

Graphs can be directed or undirected. In a directed graph each edge is assigned a direction, and so the edge or ordered pair (u, v) starts from u and ends at v.

When multiple edges connect the same set of vertices then the graph is known as a multigraph.

When its possible to traverse from any vertex to any other vertex then the graph is connected, otherwise it is disconnected. Additionally, in the special case where all vertices are connected by edges with each other that graph is considered complete.

A graph which consists only of isolated vertices, and no edges, is known as a null graph.

In some cases graphs can also be weighted. In a weighted graph each edge is assigned a positive number w called weight which specifies the "cost" of traversing through them. Graphs with no weights are unweighted.

For example:

Handshake Lemma

For any undirected graph G = (V, E):

where e is the number of edges.

Based on that theorem, for any graph the number of vertices with odd degree must be even.

RESOURCES:

References

Images

https://commons.wikimedia.org/wiki/File:Graph_example_(Graph_theory).png

Mathematical equations used in this article, have been generated using quicklatex.

Block diagrams and other visualizations were made using draw.io.

Previous articles of the series

Introduction → Discrete Mathematics, Why Discrete Math, Series Outline
Sets → Set Theory, Sets (Representation, Common Notations, Cardinality, Types)
Set Operations → Venn Diagrams, Set Operations, Properties and Laws
Sets and Relations → Cartesian Product of Sets, Relation and Function Terminology (Domain, Co-Domain and Range, Types and Properties)
Relation Closures → Relation Closures (Reflexive, Symmetric, Transitive), Full-On Example
Equivalence Relations → Equivalence Relations (Properties, Equivalent Elements, Equivalence Classes, Partitions)
Partial Order Relations and Sets → Partial Order Relations, POSET (Elements, Max-Min, Upper-Lower Bounds), Hasse Diagrams, Total Order Relations, Lattices
Combinatorial Principles → Combinatorics, Basic Counting Principles (Additive, Multiplicative), Inclusion-Exclusion Principle (PIE)
Combinations and Permutations → Factorial, Binomial Coefficient, Combination and Permutation (with / out repetition)
Combinatorics Topics → Pigeonhole Principle, Pascal's Triangle and Binomial Theorem, Counting Derangements
Propositions and Connectives → Propositional Logic, Propositions, Connectives (∧, ∨, →, ↔ and ¬)
Implication and Equivalence Statements → Truth Tables, Implication, Equivalence, Propositional Algebra
Proof Strategies (part 1) → Proofs, Direct Proof, Proof by Contrapositive, Proof by Contradiction
Proof Strategies (part 2) → Proof by Cases, Proof by Counter-Example, Mathematical Induction
Sequences and Recurrence Relations → Sequences (Terms, Definition, Arithmetic, Geometric), Recurrence Relations
Probability → Probability Theory, Probability, Theorems, Example
Conditional Probability → Conditional Probability, Law of Total Probability, Bayes' Theorem, Full-On Example