- #1

wubie

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 v**

_{0},e_{1},v_{1},e_{2},v_{2}...e_{n},v_{n}such that for 1 =< i =< n, the edge e_{i}joins vertices v_{i-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.