poor_van_buren (poor_van_buren) wrote in lhsthespians,


I know that this is completely irrelevant to anything this community is for, but either way I'm posting it. And there are two reasons for doing so: 1.) I'm bored, and 2.) it will help me study.

so then...

Preface- the symbol є means is an element of

A graph is a pair of sets (V,E) such that E={{u,v}: u,v є V}

An element of V is a vertex (V is the "groundset"), an element of E is an edge.

[Vertices are connected by edges, thereby making a graph, fairly simple.]

If e={u,v} є E(G) then: (1.) e joins u and v, (2.) e is incident with u (or v), and (3.) u is adjacent to v.

The degree of a vertex, denoted as deg(v), is the number of vertices that are adjacent to v. An isolated vertex has degree zero.

The neighborhood of a vertex is the set of vertices adjacent to it. This is denoted as N(v). Please note that deg(v)=|N(v)|, that is, the degree of some vertex v is equal to the cardinality of v's neighborhood.

The graph of G' is a subgraph of G if V(G') is a subset of V(G) and E(G') is a subest of E(G). However, if V(G') and E(G') do not form an independent graph, then G' is not a subgraph of G.

A walk in G, from u to v, is a sequence of adjacent vertices starting with u and ending with v.

A trail in G is a walk that repeats no edge.

A path in G is a walk that repeats no vertex.

A closed walk is a walk with at least one edge, and that starts and ends at the same vertex.

A circuit is a closed walk that repeats no edge. (closed trail)

A cycle is a closed walk that repeats no vertex (except the first and last, since they're the same). (closed path)

A graph is connected if there is a walk between any two vertices.

A component of a graph is a maximal connected subgraph.

That's our lesson in graph theory today, and if you actually read that, then you are a bigger loser than I am.
  • Post a new comment


    default userpic