What are the definitions of graph theory and its components?

[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 v₀,e₁,v₁,e₂,v₂...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.

 

[Ambitwistor]

But I still am having trouble with components of a graph and when a graph is connected.

Draw a graph. Next to it, draw a completely different graph. You can regard the two together as subgraphs of a combined graph --- it's just that the combined graph is disconnected: it has two pieces. Each of those pieces is a (connected) component. Every node in one of the components is connected (directly, or indirectly through some path i.e. sequence of edges) to every other node in that component, but none of them are connected to any of the nodes in the other component.

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?

Well, a multigraph with a loop is still a multigraph. The definition of pseudograph was unclear: is it a (simple) graph with loops, or a multigraph with loops? Presumably, that's why you're asking the question ... you can't tell for sure from how the definition is worded.

 

[NateTG]

Originally posted by wubie
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.

A graph is connected if there is a trail/path betwteen every pair of vertices. "Connected" means what you think it ought to mean.

A component is a maximal connected subgraph. If a graph is connected, then it only has one component -- the entire graph. Otherwise, each 'disconnected' piece is a component.

Originally posted by wubie
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?

How about both? They don't have to be exclusive.

 

[wubie]

Thankyou Ambitwistor and NateTG.

I think I understand now. I have to think about it a bit more but I believe I got it.