A complete graph is a graph where every vertex is joined to every other vertex by an edge. This concept is perhaps most useful in practice through its role in defining a clique, which is a complete subgraph.
A regular graph is a graph in which every vertex has the same degree. A regular graph with common degree d is called d-regular. An example of a 2-regular graph is the ring.
A connected graph with no cycles is called a tree. The disjoint union of such graphs is called a forest. A digraph whose underlying graph is a tree is called a directed tree. Often such trees have associated with them a special vertex called a root, which is distinguished by being the only vertex from which there is a directed path to every other vertex in the graph. Such a graph is called a rooted
tree. A vertex preceding another vertex on a path from the root is called an ancestor, while a vertex following another vertex is called a descendant. Immediate ancestors are called parents, and immediate descendants, children. A vertex without any children is called a leaf. The distance from the root to the farthest leaf is called the depth of the tree.
A k-star is a special case of a tree, consisting only of one root and k leaves. Such graphs are useful for conceptualizing a vertex and its immediate neighbors (ignoring any connectivity among the neighbors).
An important generalization of the concept of a tree is that of a directed acyclic graph (i.e., the DAG). A DAG, as its name implies, is a graph that is directed and that has no directed cycles. However, unlike a directed tree, its underlying graph is not necessarily a tree, in that replacing the arcs with undirected edges may leave a graph that contains cycles.
tree. A vertex preceding another vertex on a path from the root is called an ancestor, while a vertex following another vertex is called a descendant. Immediate ancestors are called parents, and immediate descendants, children. A vertex without any children is called a leaf. The distance from the root to the farthest leaf is called the depth of the tree.
A k-star is a special case of a tree, consisting only of one root and k leaves. Such graphs are useful for conceptualizing a vertex and its immediate neighbors (ignoring any connectivity among the neighbors).
An important generalization of the concept of a tree is that of a directed acyclic graph (i.e., the DAG). A DAG, as its name implies, is a graph that is directed and that has no directed cycles. However, unlike a directed tree, its underlying graph is not necessarily a tree, in that replacing the arcs with undirected edges may leave a graph that contains cycles.
For example,
is.dag(dg)
A bipartite graph is a graph G = (V,E) such that the vertex set V may be partitioned into two disjoint sets, say V1 and V2, and each edge in E has one endpoint in V1 and the other in V2. Such graphs typically are used to represent ‘membership’ networks, for example, with ‘members’ denoted by vertices in V1, and the corresponding ‘organizations’, by vertices in V2.
A bipartite graph is a graph G = (V,E) such that the vertex set V may be partitioned into two disjoint sets, say V1 and V2, and each edge in E has one endpoint in V1 and the other in V2. Such graphs typically are used to represent ‘membership’ networks, for example, with ‘members’ denoted by vertices in V1, and the corresponding ‘organizations’, by vertices in V2.
No comments:
Post a Comment