Question

Give a brief description of each:

Trees and forests

Vector spaces associated with a graph

Representation of graphs by binary matrices and list structures

Traversability

Connectivity

Planar graphs

Colorability

Directed graphs

Answer 1

Answer:

Trees and forests: A tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph. Forest is a collection of disjoint trees. In other words, we can also say that forest is a collection of an acyclic graph which is not connected.

Vector spaces associated with a graph: Vector spaces associated with a graph such as the vector spaces associated with the sets of cutsets, circuits, and subgraphs of graph. It is well known that the set of all subgraphs of a given graph G constitutes a linear vector space over the field of integers mod 2, where the addition of vectors is the ring-sum operation [5, 11].

Representation of graphs by binary matrices and list structures: We can represent a graph in many ways. The two most common ways of representing a graph is as follows:

1) Bianry matrices: A binary matrix is a matrix in which the cells can have only one of two possible values - either a 0 or 1. An adjacency matrix is a VxV binary matrix A. Element A_i,j is 1 if there is an edge from vertex i to vertex j else A_i,j is 0.

2) List: The other way to represent a graph is by using an adjacency list. An adjacency list is an array A of separate lists. Each element of the array A_i is a list, which contain's all the vertices that are adjacent to vertex i.

Traversability: For a graphs to be on Euler circuit or path it must be traversable. This means can you trace over all the arcs of a graph exactly once withough lifting your pencil.

Connectivity: A graph is said to be connected if there is a path between every pair of vertex. From every vertex to any other vertex, there should be some path to traverse. That is called the connectivity of a graph.

Planar graphs: In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other.

Colorability: Graph coloring is nothing but a simple way of labelling graph components such as vertices, edges, and regions under some constraints. In a graph, no two adjacent vertices, adjacent edges, or adjacent regions are colored with minimum number of colors. This number is called the chromatic number and the graph is called a properly colored graph.

Directed graphs: A directed graph is graph, i.e., a set of objects (called vertices or nodes) that are connected together, where all the edges are directed from one vertex to another. A directed graph is sometimes called a digraph or a directed network.

Please give thumbsup, or do comment in case of any query. Thanks.