# Graph theory

1. Aug 27, 2009

### ╔(σ_σ)╝

I am planing to take a course in Graph theory at my university, but i have no idea what it is.

I want to take something that is ,to some extent, rigorous and interesting.

This is the course summary provided by my school :

Introduction to graph theory and its applications with an emphasis on algorithmic structure. Topics may include graphs, digraphs and subgraphs, representation of graphs, breadth first and depth first search, connectivity, paths, trees, circuits and cycles, planar graphs flows and networks, matchings, colourings, hypergraphs, intractability and random algorithms.

From what i read this is almost like a computer science course!

I wanted to get an opinion from someone who knows a bit about graph theory. Does this sound like something that is worth taking if im looking for something rigorous and mathematical?

What exactly is graph theory ?

2. Aug 27, 2009

### Tac-Tics

It is very applicable to computer science. Graphs are particularly well suited for computer science because they are finite structured objects that easily model all kinds of real world problems.

Graph theory has a very number theoretic feel to it.

3. Aug 27, 2009

### ╔(σ_σ)╝

So, does this course sound like something worth taking, based on the course summary above ?

4. Aug 27, 2009

"Graph theory has a very number theoretic feel to it."

I'm not sure what that means, but if you go far enough into graph theory you will need some group theory and topology - at least for graduate level courses.

5. Aug 27, 2009

### ╔(σ_σ)╝

Im not sure what that means either since, i have not touched number theory.

What do you think are some courses I should have handy, in order to tackle graph theory ?

6. Aug 27, 2009

If this is a first course (I'm guessing it is, or you wouldn't have these questions) it will be self-contained. You'll see some counting methods used in proofs, and quick sketches will be used more often than, well, you can count - at least, that's my experience.

7. Aug 27, 2009

### ╔(σ_σ)╝

What do you mean by counting methods used in proofs ? and quick sketches ? Sorry, i`m oblivious as to what you mean.

8. Aug 27, 2009

### pbandjay

As far as counting methods, probably permutations and combinations. A graph is a set of vertices, some connected by what are called edges. Counting is used in counting vertices or edges in certain proofs. Since this sounds like a beginner course in graph theory, you will probably just be studying different graphs and their properties. For example, something very easy that you will probably learn is: A bipartite graph is two-colorable. Of course you probably don't know what that means, but the vocabulary is something you will also learn. Perhaps a link with more information will help...

http://en.wikipedia.org/wiki/Graph_theory

9. Aug 27, 2009

### waht

Might touch some topics from combinatorics, game theory, statistics, and linear algebra. But yeah if it doesn't cover some topology and group theory the subject is boring and dry unless you are a computer science major.

10. Aug 27, 2009

### ╔(σ_σ)╝

Thanks a lot guys. The course descriptions given on my school website could be quiet vague and ambiguous.

Hopefully it covers some topology! I need all the help I can get on topological abstractions before I take real analysis.

pbandjay I already checked it out, but it seemed like technician jargon to me.

11. Aug 27, 2009

### Elucidus

Perhaps

http://www.math.niu.edu/~rusin/known-math/index/05CXX.html [Broken]

Graph Theory works a lot with set theory, relation theory, combinatorics, some matrix algebra and algorithm complexity analysis. In an introductory course, all of the fundamentals (other than basic algebra) are typically introduced. Some courses in Graph Theory have Discrete Mathematics as a prerequisite.

--Elucidus

Last edited by a moderator: May 4, 2017