A matrix is a rectangular arrangement of numbers in rows and columns. It is used to represent data or systems of linear equations. The size of a matrix is defined as m × n, where m is the number of rows and n is the number of columns.
Example:
A = [ [1, 2], [3, 4] ] is a 2×2 matrix.
Two matrices are equivalent if one can be obtained from the other by a sequence of elementary row or column operations.
Example:
A = [ [1, 2], [3, 4] ]
B = [ [1, 2], [0, -2] ] (obtained by replacing second row with R2 - 3×R1)
Example:
Original: [ [1, 2], [3, 4] ]
Operation: R2 → R2 - 3×R1
Result: [ [1, 2], [0, -2] ]
The rank of a matrix is the maximum number of linearly independent rows or columns. By reducing a matrix to its normal form (also known as row-reduced form), we can find its rank.
Example:
A = [ [1, 2], [3, 4] ]
Reduce to normal form:
→ [ [1, 2], [0, -2] ] → [ [1, 2], [0, 1] ]
Rank = 2
A matrix is in echelon form if all nonzero rows are above any rows of all zeros, and the leading entry of each nonzero row is to the right of the leading entry of the row above it. The number of non-zero rows gives the rank.
Example:
A = [ [1, 2, -1], [2, 4, 3], [1, 1, 1] ]
→ Row reduce to echelon form
→ [ [1, 2, -1], [0, 0, 5], [0, 0, 0] ]
Rank = 2
Connectives are logical operators used to combine statements or propositions. The most common connectives are:
A statement formula is a combination of logical variables (propositions) connected by logical connectives. Example:
Example: (P ∧ Q) → (R ∨ S)
Tautology: A statement that is always true, regardless of the truth values of the individual propositions.
Contradiction: A statement that is always false, regardless of the truth values of the individual propositions.
Example of Tautology: P ∨ ¬P (Always true)
Example of Contradiction: P ∧ ¬P (Always false)
Equivalence formulae show when two formulas are logically equivalent. This means that both formulas have the same truth value in all cases. Examples of equivalence:
Conjunctive Normal Form (CNF): A logical formula is in CNF if it is a conjunction of disjunctions of literals. Example:
Example: (P ∨ Q) ∧ (¬P ∨ R)
Disjunctive Normal Form (DNF): A logical formula is in DNF if it is a disjunction of conjunctions of literals. Example:
Example: (P ∧ Q) ∨ (¬P ∧ R)
Inferences in logical statements are derived from premises using rules of logic. A statement can be validated using truth tables to determine its validity.
Example: To validate P → Q using a truth table:
| P | Q | P → Q |
|---|---|-------|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
A graph G is a set of vertices (nodes) and a set of edges (lines) connecting some or all of the vertices. It is written as G = (V, E), where:
Finite Graph: A graph with a finite number of vertices and edges.
Example: V = {A, B, C}, E = {(A, B), (B, C)}
Infinite Graph: A graph with an infinite number of vertices and/or edges (not common in simple graph theory).
Incidence: An edge is said to be incident to a vertex if the vertex is one of its endpoints.
Degree: The degree of a vertex is the number of edges incident to it.
Example: If vertex A connects to B, C, and D, then deg(A) = 3
A null graph is a graph that has vertices but no edges.
Example: V = {A, B, C}, E = {}
A subgraph is a graph formed from a subset of vertices and edges of a given graph.
If G has V = {A, B, C, D}, E = {(A, B), (B, C), (C, D)},
Then a subgraph H can be: V = {A, B, C}, E = {(A, B), (B, C)}
Example:
Walk: A → B → C → A
Path: A → B → C
Circuit: A → B → C → A
Connected Graph: A graph is connected if there is a path between every pair of vertices.
Disconnected Graph: A graph that is not connected; it has at least two vertices with no path between them.
Connected: A - B - C
Disconnected: A B - C (no edge connecting A to others)
A Euler Graph is a graph in which a path exists that visits every edge exactly once. The graph must satisfy two conditions:
Example: A - B - C - A (Euler Path exists)
Hamiltonian Path: A path in a graph that visits every vertex exactly once.
Hamiltonian Circuit: A Hamiltonian Path that starts and ends at the same vertex, forming a cycle.
Example of Hamiltonian Path: A → B → C → D
Example of Hamiltonian Circuit: A → B → C → D → A
A tree is a connected graph with no cycles. It has the following properties:
Example: A tree with 3 vertices and 2 edges:
A
/ \
B C
This graph is a tree, as it is connected and acyclic. It has 3 vertices and 2 edges.
Distance: The distance between two vertices is the number of edges in the shortest path between them.
Centre: The centre of a tree is the set of all vertices that are at an equal or minimal distance from all other vertices.
Example: In the tree:
A
/ \
B C
/ \
D E
The distance between vertex A and D is 2 (A → B → D).
The centre of the tree would be vertex B because it minimizes the maximum distance to all other vertices.
Rooted Tree: A tree with a specific vertex (the root) from which all other vertices are descended.
Binary Tree: A rooted tree where each vertex has at most two children.
Example: Rooted tree:
A
/ \
B C
/ \
D E
Example: Binary tree:
A
/ \
B C
In a binary tree, each node can only have two children (left and right).
Spanning Tree: A subgraph that includes all vertices of the original graph and is a tree.
Fundamental Circuit: A cycle formed by adding an edge to a spanning tree.
Example: For the graph:
A---B
| |
C---D
A spanning tree could be:
A---B
|
C
Adding the edge D-A creates a fundamental circuit:
A---B
| |
C---D
Cutset: A set of edges whose removal disconnects the graph.
Properties: Removing a cutset disconnects the graph, and every tree has at least one cutset.
Example: In the graph:
A
/ \
B C
The cutset is {(A, B), (A, C)} because removing these edges disconnects the graph into separate components.
The matrix representation of a graph can be done using several types of matrices:
Example of an Adjacency Matrix:
A B C D
A [0, 1, 1, 0]
B [1, 0, 0, 1]
C [1, 0, 0, 1]
D [0, 1, 1, 0]
Here, 1 indicates an edge exists between the vertices, and 0 indicates no edge.
Planar Graph: A graph that can be drawn on a plane without any edges crossing.
Kuratowski's Theorem: A graph is non-planar if it contains a subgraph that is a subdivision of K5 (the complete graph on 5 vertices) or K3,3 (the complete bipartite graph on 3 vertices and 3 vertices).
Example: Planar Graph:
A---B
| |
C---D
This graph can be drawn without edges crossing, so it's planar.
Non-planar Graph:
K5 (Complete graph on 5 vertices)
This graph can't be drawn on a plane without edges crossing.
To detect if a graph is planar, algorithms like Kuratowski's Algorithm or Euler's Formula are used. Euler's formula states that for a planar graph with V vertices, E edges, and F faces, the following holds:
V - E + F = 2
Example: For the planar graph above, if we have 4 vertices, 4 edges, and 1 face (the outer region), we get:
4 - 4 + 1 = 2
This satisfies Euler's formula, confirming the graph is planar.
A directed graph or digraph is a graph in which edges have a direction. That means an edge connects one vertex to another in a specific direction. These directed edges are often represented by arrows.
Example:
Consider a directed graph where:
- Vertices: A, B, C
- Edges: (A → B), (B → C), (C → A)
Example:
- Simple Digraph: A → B → C → A
- Weighted Digraph: A → B (weight: 5), B → C (weight: 3), C → A (weight: 2)
A binary relation on a set is a relation between elements of the set. In the context of digraphs, a directed edge from vertex A to vertex B represents a binary relation from A to B.
Example:
- Set of vertices: {A, B, C}
- Binary relation R: (A → B), (B → C)
A directed path is a sequence of vertices such that there is a directed edge from one vertex to the next. A digraph is connected if there is a directed path between any two vertices.
Example:
In the directed graph:
A → B → C → A
There is a directed path between A and B, B and C, and C and A, so the graph is connected.
An Eulerian Digraph is a digraph in which there exists a Eulerian path (a path that visits every edge exactly once) or a Eulerian circuit (a circuit that visits every edge exactly once and returns to the starting vertex).
Conditions for an Eulerian Digraph:
Example:
- Eulerian Circuit: In a digraph with vertices A, B, C:
A → B → C → A
This digraph has an Eulerian circuit because every edge is visited exactly once, and the path returns to A.
A directed tree is a type of digraph that is connected and has no cycles. The edges have directions, and there is one root vertex that can reach all other vertices by following directed edges.
Example:
Consider a directed tree with:
A
/ \
B C
Here, A is the root, and B and C are connected by directed edges from A to them.
A fundamental circuit in a digraph is a cycle that is formed by adding one edge to a spanning tree (the edges of a tree that connect all vertices).
Example:
In a digraph with the following structure:
A → B → C → A
There is a fundamental circuit: A → B → C → A.
An adjacency matrix is a way to represent a digraph. Each element in the matrix indicates whether there is an edge between two vertices.
For a directed graph with vertices A, B, and C, the adjacency matrix looks like this:
A B C
A [0, 1, 0]
B [0, 0, 1]
C [1, 0, 0]
This matrix shows:
- There's a directed edge from A to B.
- There's a directed edge from B to C.
- There's a directed edge from C to A.