Chromatic Properties of House and House X Graphs

As with Bull Graphs, House Graphs are simple graphs (not the Graph Theoretic definition) which have been neglected. They may not be interesting or yield any important findings to professional research mathematicians, but I haven't been able to find a paper or website which lists or shows any of the House Graphs properly at all. My intention is simply to state and prove of these properties.

Please note I'm not a professional mathematician and I'm not even studying for a Mathematics degree (Computer Science), and therefore may make mistakes or misunderstandings.

There are two main variants of House Graphs, and in this article I will listing the Vertex Colouring and Edge Colouring properties of such graphs. The two graphs are the House Graph and the House-X Graph.

House Graph

House-X Graph

Both of the graphs are simple graphs, and the same number of vertices. In terms of the structure of the graph, the only difference between the graphs are the number of edges. The number edges for the House Graph is 6 and the number of edges for the House-X Graph is 8. The number of edges will be fundamental to the chromatic properties of these graphs.

 Chromatic Number:

The Chromatic Number is defined to be the minimum vertex colouring of a graph G. $$\chi(G)$$ is the common notation for the chromatic number of a given graph called G. The minimum vertex colouring is the smallest number of k-colours needed to colour the vertices, so that no two adjacent vertices contain the same colour; no two vertices connected by a common edge have the same vertex colour.

The chromatic number of a House X Graph is 4, this is very obvious, because the chromatic number of a complete graph with n vertices is n. The House-X Graph contains a complete graph of 4 vertices, and the addition of a 'isolated' single vertex creates a chromatic number of 4. 

The chromatic number of the House Graph is 3, for a one main reason, the 3-Complete Graph is a subgraph of the House Graph which leads to the fact at least three colours to required. This isn't really a rigorous proof as such, but by attempting to colour the graph with only 2 colours, the idea will become more apparent.

Chromatic Index:

The Chromatic Index of a graph is defined to be the minimum edge colouring of a graph G. The edge colouring of a graph, is when two or more edges incident to a common vertex do not share the same edge colour. Since the House-X Graph and the House Graph are both simple graphs, then Vizing's Theorem can be applied here to show the chromatic index of both graphs.

Vizing's Theorem states that the minimum number of colours needed to edge colour a graph is the maximum degree or the maximum degree with the addition of 1. The maximum degree of a graph is the largest degree of a vertex within the graph. The degree is the number of edges incident to that vertex.

The House Graph has a chromatic index of 3, and the House-X Graph has a chromatic index of 4. The chromatic index for the House Graph is mostly due to the 3-Complete Graph being present as a subgraph, and the fact that Complete Graphs on odd n vertices will have a chromatic index of n.

Reference(s):

House Graph -- From Wolfgram MathWorld

Discrete Geometry - Bin Packing Problem

This post is a little irrelevant to general contents of my blog, but I found this to be a interesting geometry problem and it does have some ties with Computational Geometry, which is form a of theoretical computer science. There is additionally some connection with Computational Complexity Theory too. The Bin Packing Problem isn't difficult to explain, and yet can be difficult to find a optimal solution.

With Discrete Mathematics, I personally find that the branches within this field are more accessible but the problems are difficult enough to be interesting and form a field of serious mathematical study. I'm only a amateur mathematician and a student, so if there are any problems then please highlight them in the comments section.

Bin Packing Problem:

The Bin Packing Problem is an example of a optimization problem which has a surprisingly large number of applications, especially in logistics and data management. The Bin Packing Problem asks to minimize the number of bins needed to pack a certain number and given volume for a list of objects. These objects can vary in size, but the bin volumes will remain fixed. There are some programs which will give valid suggestions for the most optimal method, however, the problem is a NP- Hard Combinatorial class type.

The sum of the sizes of the items must be less than or equal to the total volume of the bins being used. The size of the items can never be greater than the total volume of the bins. If the volume of one bin is reached, then a new bin will need to be used. The problem looks to find a packing method which will reduce the number of bins needed to provide a optimal method.

The First-Fit Algorithm is the best algorithm which has been used for the bin packing problem. The First-Fit Algorithm is an example of a greedy approximation algorithm, in that the items will processed in any given order. The algorithm will place as many items as possible into the first bin, and then create a new bin if no other additional bins can be found. The process is then repeated for the rest of the items.

The First-Fit Algorithm has a approximation factor of 2 (APX). The approximation factor is used for NP-Hard problems, since it is very unlikely that a efficient algorithm will be produced to solve the problem directly, and therefore a P class algorithm can be developed in order to find a approximate answer. The approximation factor of 2, means that the algorithm will never use more than twice the number of least bins needed for the bin packing problem. For instance, if the number of bins needed was 2, then the algorithm will never use more than 4.

References:

Bin Packing Problem

Mathematics for Theorectical Computer Science

I thought I would create a list of Maths topics which were relevant for those who are wishing to study Computer Science. I've seen most people on online communities referring to topics which have very little relevance or completely pointless in relation to Computer Science. This list is based upon my experiences and a friend who studies Computer Science at University. I've listed the most popular Computer Science fields and their Maths topics below.

General Computer Science:

These are the topics which you will typically study in your first year, and therefore will have to do.

• Graph Theory
• Linear Algebra (Matrices and Vectors)
• Calculus I and maybe some Calculus II
•  Analytical Geometry
• Set Theory
• Big O Notation
• Radicals, Logarithms and Polynomials
• Logic

Computer Graphics: 

I'm not too sure about Graphics, but these are the subjects which do have some relevance.

• Fractal Geometry
• Linear Algebra
• Analytical Geometry
• Differentiable Geometry
• Hyperbolic Geometry
• Differential Equations
• Functional Analysis

Information Theory:

• Differential Equations
• Real and Complex Analysis - Fourier Series
• Calculus II and Calculus III - Taylor Series
• Probability Theory

Algorithms and Data Structures:

Most algorithms are used to solve mathematical problems, rather than the algorithms you see in commercial programs.

• Graph Theory
• Number Theory
• Combinatorics
• Probability Theory
• Big O Notation
• Set Theory

Cryptography and Computational Number Theory: 

• Number Theory

Computability Theory, Computational Complexity Theory and Automata Theory:

•  Logic
• Set Theory
• Calculus I
• Recursion
• Proof Writing Techniques
• Number Theory
• Big O Notation 
• Probability Theory

In general, it's best to study Discrete Mathematics rather than Continuous Mathematics. There's some fields like Abstract Algebra which are used in Algebraic Coding Theory. Furthermore, Discrete Geometry has its applications too. Continuous Mathematics encompasses areas like Calculus/Analysis and Topology etc.
 

Data Structures - Red and Black Trees

Graph Theory Related Concepts:

Before explaining the concept of Red and Black Trees and some of the algorithm analysis related to Red and Black Trees. It's best to have a understanding of some basic Graph Theory, such as what is a tree and the colouring nodes (or vertices). Graph Theory is my favorite area of Mathematics, and has many applications in Computer Science and other subjects. Graph Theory is a very visual form of Mathematics, much like Geometry, and for those who enjoy those types of Mathematics may also enjoy Graph Theory.

A graph G is a ordered pair (V,E), with V being the graph's set of vertices and E being the the graph's set of edges which connect each vertex. Most graphs will have this basic structure, and it's the connections within the vertices which give graph their interesting properties. Hypergraphs are very interesting type of graph in my opinion, and sit between the boundary of Set Theory and Graph Theory. I may talk about more in the future.

Hypergraph

I'm going to skip most of the introductory topics of Graph Theory, which doesn't really apply to within this context.  A tree is a connected undirected graph (no arrows with the edges) with no simple cycles.

Tree T(9,8)

 Vertices within Trees are called Nodes, and each node has been labelled with a corresponding integer. We could label these nodes with any labels we so wish, such as locations within a Computer Network or Cities on a map (some applications of Graph Theory). A Red and Black Tree has the same structure, however, the nodes are coloured with Red or Black, hence the name for a Red and Black Trees. Before we continue, it's best to understand the terms Simple, Cycle and Connected. Graph Theory is very intuitive in terms of definitions and so it should be very easy to understand.

 A graph is simple if it contains no multiple edges between any two adjacent vertices, or loops (edges which loop onto the same vertex). A graph contains a cycle if there exists a path between at least two vertices within the graph, and the starting and ending vertex are the same. A cycle has no repeated edges or loops. A graph is connected if there exists a path between any two vertices. There is much more to the definitions which I have just given, however, the definitions are suffice for the topic which I'm going to explore.

There is one last Graph Theoretic definition which we must understand before we should learn about Red and Black Trees, and that is the concept of Chromatic Graph Theory, which looks at the idea of giving vertices, edges and faces within a graph distinct colours or groups of colours with certain rules to other vertices and edges within the same graph. A very famous problem was the Four-Colour Theorm.

With Red-Black Trees, the graphs use Vertex Colouring, which is as the name suggests, the colouring of vertices with a certain colour. If no two vertices connected by the same edge i.e any two vertices which are adjacent; do not have the same vertex colour, then the colouring within the graph is proper vertex colouring, which is simply called colouring. However, please bear in mind, that in this context, colouring simply refers to giving each node within the tree a colour: Red or Black. The Chromatic Polynomial can be used to calculate the possible number of proper vertex colourings for a graph.

Now, we understand the basic concepts for the theory of Red-Black Trees, which can examine the properties and algorithm mechanism of this data structure.

Red-Black Trees

There are several key properties to remember when examining Red-Black Tree data structures, since these properties will constitute which nodes are rotated when new data is inserted into the tree.

Properties: 

1. The root is black. This is the uppermost node. The rest of the nodes are considered Children of the root.
2. Every red node must have two black child nodes.
3. A node is either red or black.
4. All leaves (NIL) are black. A leaf is a vertex or node which has the degree of 1 (one edge connected to the vertex).
5. Every simple path from any given node through it's subsequent leaves contains the same number of black nodes.

 The tree will be rotated and nodes will be changed to ensure that these properties are maintained. The number of black nodes on the path from the root to a leaf is known as the black height of the tree.

Insertion:

For the insertion of new data into the tree, the complexity of this operation is O(log n) for both Average and Worst Case situations. To insert new data into the tree, we must check for a insertion point, which will one of the NIL nodes. Once the insertion point has been found (sentential node), then the new node will be coloured red and the properties of the tree will be checked. The parent node of the newly inserted node will be checked, and recoloured if needed. Rotations on the tree may be performed to validate the other properties of the tree.

Deletion:

The complexity of deletion is again O(log n) for both cases. The deletion of nodes follows a similar process as before.

Space:

The data structure uses very little memory, and has a space complexity of O(n) in both Average and Worst Case.

References:

Sorting and Searching Algorithms - The Cookbook
Red-Black Tree Wikipedia
Graph Theory (Graduate Texts in Mathematics) - Reinhard Diestel 

Deterministic Polymonial Time (P) and Non-Deterministic Polymonial Time (NP)

This is going to be a short description of the difference between P and NP time complexity classes, and what the time complexity classes are based upon. These are used for Computational Complexity and Algorithm Analysis. Computability Theory is mainly concerned with what is computable, rather than how feasible that computation is.

The P and NP time complexity classes are commonly based upon Deterministic and Non-Deterministic Turing Machines. These machines use similar mathematical notation to other models of computation, but are slightly more complex and have a larger application to other areas of Computer Science, and that is one of the reasons why I prefer to look at Turing Machines rather than Finite-State Automata.

The P complexity class is a class of decision problems (Yes or No on some input), which are solvable within Polynomial Time on a Deterministic Turing Machine. It is given by P(n) or just P, where is the number of inputs. On the other hand, NP is the complexity class of decision problems which are solvable within Polynomial Time but on a Non-Deterministic Turing Machine, and therefore given by the NP(n) or simply NP notation.

In general terms, it is considered that P is a feasible complexity class for decision problems. With both classes, the running time of the algorithm is said to increase polynomially as the size of input increases.

The Y-Axis is Time, and the X-Axis is the Input Size.

NP-Completeness and NP-Hard

Given a decision problem A and another problem B, the decision problem A is considered NP-Hard, if for every B which belongs to NP, and B is reducible to A. If A is NP-Hard and and belongs to NP, then A is considered to be NP-Complete. NP-Complete algorithms infer that there is no P version of that such algorithm. They may also be considered the hardest problems within NP.

References:

NP (Complexity)
P (Complexity)

Automata Theory - Finite State Automata and Regular Languages

Automata are abstract models of automatic machines which tend to have a very limited number of states they can be in. We use Automata without even knowing it, the most common example I can think of is the use of compilers with programming languages. In this post I'm going to be looking at Deterministic and Non-Deterministic Finite State Automata, and Regular Languages.

Firstly, I believe it would be best to give an introduction to the concept of Formal Languages which are processed by these abstract models of computation which represent real life computers in our modern age.

All the Formal Languages are defined within the Chomsky Hierarchy, which defines which languages can be computed by which machines. It takes the following format.

The hierarchy gives the types of languages classes, and what machines they can be computed by. For example, Finite Automata can only recognise Regular Languages and not Context-Free Languages. So what is the formal definition of a Formal Language?

Regular Languages and Regular Grammar: 

A formal language is a set of strings over a given alphabet with some form of rules applied to this strings. I'll introduce the terms of strings and alphabets shortly. These rules may be regular grammar which forms the basis of regular languages, which are recongised by finite automata machines. In mathematical terms, the formal language can be defined as follows:

$$L = \Sigma \subset \Sigma^*$$

A language is a set of all the possible words or strings which can be generated from that finite alphabet. Since I will be mostly looking Finite Automata, then a I mention briefly what a Regular Language is.

A Regular Language is a language which is constrained by the rules of regular grammar; all finite languages are regular, and all languages which can be accepted by a finite automation are regular, since finite automata only has a finite amount of memory, it isn't able to recognise a set of strings which has a arbitrary number of 0's or 1's.

A classic example of a regular language which can't be accepted by finite automata is:

$$\{0^n1^n | n \ge 0\}$$

Regular Languages are defined by regular expressions, regular expressions are said to be a sequence of characters which forms some kind of search pattern, for example a character can have literal meaning and a special meaning (forming a metacharacter). The pattern is a method of giving a set of strings some form of meaning and purpose. A good example from Wikipedia is, a literal character a can be used to denote the a set only containing the letter a, which would mean this: $$\Sigma = \{a\}$$

Let's give a formal definition for the rules of a regular grammar which is used to define a regular language.

A grammar tends to form a four tuple of:

$$G = (N, T, R, s)$$

The N represents a set of non-terminal symbols and the T represents a set of terminal symbols, these symbols are used to produce the production rules, which in turn are used to produce the strings accepted by the machines. Remember these are abstract representations of how computers work and how compilers can be designed. R is the production rules, and s is the start symbol.

The sets of both Non-Terminal and Terminal symbols is disjoint, and their intersection is the empty set. The Terminal Symbols can't be converted into a different character, and thus the reason why they're called Terminal Symbols. The Non-Terminal Symbols can be converted into different characters. For example, let's say that the N = {x} and T = {a}, this is a very small set but the production rules will easier to understand with less symbols.

The production rules would be defined in the following format:

$$x \rightarrow xa$$
$$x \rightarrow a$$

The production rules could be chosen a k number of times, which would produce:

$$xa^ka$$  

Deterministic and Non-Deterministic Finite State Automata:

A Deterministic Finite State Machine (DFSM) is said to be deterministic if for a given state and input, the next state can be determined. This is what most of our computers are, and hence the reason why the P=NP problem hasn't been solved, NP algorithms require a non-deterministic Turing Machine. A FSM is typically defined as a tuple:

 $$(X, Q, q, F, \sigma)$$

X = Alphabet (Inputs)
Q = Finite Set of States
q = Initial State (member of Q)
F = Final Accepting State (Proper Subset of Q)


DFSMs have a finite number of states, and their transition function is defined below:

$$\sigma: Q \centerdot X \rightarrow Q$$

The transition function shows that for a given state and a given input, which state the finite machine will move to. All FSMs have a starting state and a accepting final state. The only difference between a DFSM and a NDFSM (Non-Deterministic Finite State Machine) is the transition function used. The transition function for a NDFSM is defined below:

$$\sigma: Q \centerdot X \rightarrow P(Q)$$

With a Non-Deterministic Finite State Machine, then two states can be reached with the same input, this doesn't necessarily mean that two accepting states could be reached. With the case of one accepting state, then the machine will need process both of transition functions, and then accept the transition function which leads to a final accepting state. There is also no difference in terms of computing power between a DFSM and a NDFSM, since both machines can accept all regular languages.

The circle with a inner circle is the final accepting state, and is used with all FSM diagrams. Note that the labels on the edges represent the characters with the string being read by the machine.

Quantum Computation - Basics of Qubits

I'm still in a hiatus at the moment, but I may write the occasional blog post now and again (during the hiatus) like in this example. I will be giving a brief insight into the concept of Qubits which is the analogue to Classical Bits (1's and 0's). The only real difference between the two types, is that Qubits can be manipulated and controlled by the laws of Quantum Mechanics such as Superposition and Quantum Entanglement; the Spin states are also of great importance here since the control of the Spin will help create strings of information which are studied in Quantum Information Theory.

Before reading this post, I will assume you have some mathematical knowledge of Linear Algebra and Dirac Notation. Otherwise, I'll explain the concepts as a I write about the fundamentals of Qubits.

Firstly, let's look at the concept of Spin. Spin is a very important concept for Qubits. Spin is the angular momentum of a particle intrinsic (property of itself) to it's body. Spin is often regarded as a vector in three dimensional space, and being in the Up or Down state. The Down state has less energy in comparison to the Up state, and with Qubits, the Down state is usually set and then the Spin state will be changed to the Up state by electromagnetic radiation when necessary. The notation below represents a state vector called a Ket.

$$\vert A>$$

The Ket vector can be used to represent Spin states, and commonly denoted in the following form: 

<u|A> for an Up state and <d|A> for a Down state. The lowercase a and d actually represent the probability amplitudes of the particle being in those two quantum states. Of course, the particle can be in a superposition of those two quantum states, but under observation this coherence is usually broken and the particle is measured as being in one quantum spin state. The probability amplitudes are typically complex numbers, which means they have a real part and imaginary part.

To gather the probability of spin we square these probability amplitudes to give the following notation:

$$\lvert d^2 \rvert$$ and $$\lvert u^2 \rvert$$ which will need to equal 1.

More specifically, the two quantum states are called basis vectors, and can be represented as |0> and |1>. Thee basis is simply all the possible vectors for a particular vector space. I will assume you will know the formal definition of a basis.

Another two important points are the Bloch Sphere and Quantum Entanglement. Quantum Entanglement means if we change the state of one particle then it will change the state of a another particle which is entangled with the first particle. This is a fundamental idea to Quantum Computing. It enables us to compute a larger number of bits simultaneously. For example, a Qubit has two basis states: |0> and |1>, or more correctly as: |00> and |11> since a Qubit can be in superposition of two states at once. Remember that when we measure or observe the state, it will be in one state. If we change one Qubit to |00> then the other Qubit will change to |00> too. There is equal probability of the Qubit being in the superposition of |00> or |11>.

A important point to remember is that, for every additional Qubit you add, the computing power in comparison to a Classical Computer is doubled like so:

$$2^n$$
n is the number of Qubits. If we had 3 Qubits, then classically this will be equivalent to 8 Classical Bits.

Typically, Qubits are represented as a Bloch Sphere, since Qubits exist in a two-dimensional Hilbert Space where only the superposition of two quantum states is possible. In later posts I will attempt to explain the Bloch Sphere in more depth.

This post was only supposed to be very introductory, and not go into depth about Qubits and Quantum Computation. In the future, I will build upon this post and go into more depth about Quantum Computation and other theoretical concepts.