Sunday, December 31, 2017

Metric properties of graphs

Given a connected graph, we can form a metric space from the graph in which the distance between any two points is determined by the shortest path between them. The shortest path between two points need not be unique, unless the graph is a geodetic graph. This metric space is always going to be a discrete space, and a very particular type of discrete space which is generated by the unit distances between its points. The most interesting metric property of any vertex in a graph is its eccentricity which is the greatest distance between the vertex and any other point. The radius and the diameter of a graph are distance related properties determined by the minimum and the maximum eccentricity respectively.

Thursday, August 24, 2017

Geodetic graphs

Geodetic graphs have the particular property that each pair of points has a unique shortest path between them, or geodesic. Trees are a special case of geodetic graphs in which each pair of points has a unique path in general between them. Block graphs are sometimes called clique trees, they include trees and also happen to be the chordal geodetic graphs.

Monday, April 3, 2017

Partition logic

The logic of set partitions is a fundamental part of the analysis of ordering relations. The set partitions necessarily form a lattice which has certain properties corresponding to its join and meet operations. At the same time, the elements themselves form a Moore family depending upon which direction you intend to take the ordering. The Moore family then necessarily comes with a corresponding closure operation.

Sunday, January 1, 2017

2016 year in review

The methods of propositional logic can be applied to situations that arise from boolean algebra. Boolean formulas are applicable to any boolean algebra structure rather it is booleans themselves or sets, classes, and other predicate like structures. Set theoretic operations like union, intersection, difference, and symmetric difference can be expressed in terms of boolean formulas. These set theoretic operations are not unlike the logical connectives defined by these same boolean formulas.

At the same time, a wide variety of constraint satisfaction problems like sudoku can be expressed in terms of boolean formulas. Boolean formulas defined by clauses that have no more then two elements are equivalent to implication graphs. Backtracking search methods can be used to solve constraint satisfaction problems like sudoku and implications can be used to narrow down the search space for any partial candidate solution in the backtracking search.

The exact solutions to constraint satisfaction problems can therefore be deduced. In the vast majority of cases exact constraint satisfaction methods are not applicable and we need to use heuristics and statistics instead to get approximate solutions to optimization problems.