Keterhubungan Graf dengan Aljabar Matriks

Abstract

Let G be a graph consisting of n vertices and m edges, a graph G is said to be connected if G contains exactly one connected component, and is said to be disconnected otherwise. A simple graph G can be represented as an incidence matrix B = [biJJ. Suppose each edge in G is assigned an arbitrary orientation so as to obtain an orientation digraph D, an orientation digraph D of a graph G can be represented in the form of matrix Q = [qij], where Q is said to be the orientation matrix of the graph G. In this research, a criteria for the connectedness of a graph using the rank of a matrix has been obtained, i.e. a graph is said to be connected if the rank of matrix Q is n-1. However, a graph is said to be disconnected if the rank of the Q matrix is less than n-1.