Results 1 to 3 of 3

Math Help - Question about graph

  1. #1
    Newbie
    Joined
    Jul 2011
    Posts
    7

    Question about graph

    The question is Calculate the maximum number of edges in a simple graph with nnodes and k components.

    I dont really understand what the question means .. and how to solve this..

    Thanks...


    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,669
    Thanks
    1618
    Awards
    1

    Re: Question about graph

    Quote Originally Posted by kakatomy View Post
    [FONT=arial]The question is Calculate the maximum number of edges in a simple graph with nnodes and k components.
    I dont really understand what the question means .. and how to solve this..
    A component is a maximally connected subgraph of a graph.
    You need to check your text material. Some authors allow degenerate components, one vertex, most do not.

    Here is an example: Consider a twelve vertex graph with three components having three, four and five vertices.
    Then the graph could be K_3\cup K_4\cup K_5.
    That is a maximum of 3+6+10=19 edges in all.

    That said, I don't know how to solve the general case.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2011
    Posts
    7

    Re: Question about graph

    Quote Originally Posted by Plato View Post
    A component is a maximally connected subgraph of a graph.
    You need to check your text material. Some authors allow degenerate components, one vertex, most do not.

    Here is an example: Consider a twelve vertex graph with three components having three, four and five vertices.
    Then the graph could be K_3\cup K_4\cup K_5.
    That is a maximum of 3+6+10=19 edges in all.

    That said, I don't know how to solve the general case.

    The question didnt provide anything else so I also dont understand the question....

    SOsad
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Question
    Posted in the Calculus Forum
    Replies: 0
    Last Post: December 9th 2008, 11:14 AM
  2. Graph question
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: August 23rd 2008, 08:06 PM
  3. Graph question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 20th 2008, 06:51 AM
  4. graph question
    Posted in the Calculus Forum
    Replies: 1
    Last Post: September 29th 2007, 04:19 PM
  5. Graph question, please help
    Posted in the Calculus Forum
    Replies: 1
    Last Post: September 25th 2007, 08:53 PM

Search Tags


/mathhelpforum @mathhelpforum