- #1
wubie
Hello,
My discrete math course has begun a section on graph theory. And I am hung up on some of the definitions. If someone is familiar with graph theory, I would appreciate it if some of these definitions could be reworded in another way. I will post the definitions we have taken so far and highlight the definitions with which I am having trouble.
SIMPLE GRAPH - is formally defined as an ordered pair (V,E) where V is a nonempty set of elements called vertices and E is a set of two-element subsets e = {u,v} of V called edges.
If some pairs of vertices have more than one edge joinging them, the result is called a MULTIGRAPH.
If there are loops ( which are edges beginning and ending at the same vertex) the result is called a PSEUDOGRAPH.
SUBGRAPH - of a graph is a set of vertices and edges, provided that all vertices incident with edges in the subgraph are included. In other words, a subgraph is a subset of the vertices and edges that itself forms a graph.
Types of Subgraphs
WALK - is a subraph that consists of a sequence of vertices and edges v0,e1,v1,e2,v2...en,vn such that for 1 =< i =< n, the edge ei joins vertices vi-1 and i.
TRAIL - a walk in which no edges are repeated.
PATH - a trail in which no vertices are repeated except perhaps for the first and last vertex.
CIRCUIT - is a trail whose first and last vertices are the same.
CYCLE - is a path whose first and last vertices are the same.
Components of a Graph - Two vertices of a graph that are joined by a path are said to belong to the same component of the graph. If the whole graph is one component, then it is said to be connected.
I definition of a walk is making more sense to me now that I have written it out here. But I still am having trouble with components of a graph and when a graph is connected.
I also would like to know, if a graph is considered a multigraph, but it also has a loop, is it a multigraph or a pseudograph?
Any help is appreciated. Thankyou.
My discrete math course has begun a section on graph theory. And I am hung up on some of the definitions. If someone is familiar with graph theory, I would appreciate it if some of these definitions could be reworded in another way. I will post the definitions we have taken so far and highlight the definitions with which I am having trouble.
SIMPLE GRAPH - is formally defined as an ordered pair (V,E) where V is a nonempty set of elements called vertices and E is a set of two-element subsets e = {u,v} of V called edges.
If some pairs of vertices have more than one edge joinging them, the result is called a MULTIGRAPH.
If there are loops ( which are edges beginning and ending at the same vertex) the result is called a PSEUDOGRAPH.
SUBGRAPH - of a graph is a set of vertices and edges, provided that all vertices incident with edges in the subgraph are included. In other words, a subgraph is a subset of the vertices and edges that itself forms a graph.
Types of Subgraphs
WALK - is a subraph that consists of a sequence of vertices and edges v0,e1,v1,e2,v2...en,vn such that for 1 =< i =< n, the edge ei joins vertices vi-1 and i.
TRAIL - a walk in which no edges are repeated.
PATH - a trail in which no vertices are repeated except perhaps for the first and last vertex.
CIRCUIT - is a trail whose first and last vertices are the same.
CYCLE - is a path whose first and last vertices are the same.
Components of a Graph - Two vertices of a graph that are joined by a path are said to belong to the same component of the graph. If the whole graph is one component, then it is said to be connected.
I definition of a walk is making more sense to me now that I have written it out here. But I still am having trouble with components of a graph and when a graph is connected.
I also would like to know, if a graph is considered a multigraph, but it also has a loop, is it a multigraph or a pseudograph?
Any help is appreciated. Thankyou.