1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph theory

  1. Aug 27, 2009 #1
    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 i`m looking for something rigorous and mathematical?

    What exactly is graph theory ?

    Any helpful comments would be appreciated.
  2. jcsd
  3. Aug 27, 2009 #2
    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.
  4. Aug 27, 2009 #3
    So, does this course sound like something worth taking, based on the course summary above ?
  5. Aug 27, 2009 #4


    User Avatar
    Homework Helper

    "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.
  6. Aug 27, 2009 #5
    I`m 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 ?
  7. Aug 27, 2009 #6


    User Avatar
    Homework Helper

    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.
  8. Aug 27, 2009 #7
    What do you mean by counting methods used in proofs ? and quick sketches ? Sorry, i`m oblivious as to what you mean.
  9. Aug 27, 2009 #8
    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...

  10. Aug 27, 2009 #9
    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.
  11. Aug 27, 2009 #10
    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.
  12. Aug 27, 2009 #11

    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.

    Last edited by a moderator: May 4, 2017
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Graph theory
  1. Graph Theory (Replies: 3)

  2. Graph theory (Replies: 5)

  3. Graph Theory (Replies: 3)

  4. Graph Theory (Replies: 1)