Discrete Math- Number of factor trees of a graph

1)Find the number of factor trees of the graph below

2)Given the graph G of the figure below. What is the number of factor trees of G that contain the path 2-3-4-5-6-7-11 ?

3)Suppose we want to schedule the courses of the exam period so that there is no student who has two courses on the same day. The data is as follows: we have the courses numbered with numbers 1,2,...,7 and the diagram below which shows if there is a student enrolled in two courses at the same time. More specifically, if there is an asterisk in position i,j, this means that there is a student enrolled in course i and course j at the same time. What is the minimum number of days we need to schedule the exams?

4)Let T be a tree with 20 vertices, for which we know that each vertex has degree either 1 or 4. We want to add to this tree the minimum number of edges possible (without adding extra vertices) so that the resulting graph has an Euler cycle . How many edges should we add?

Pictures down below for each question

  • For a collection of four high level graph theory questions, the offered bounty is low!

  • Kratos Kratos
    0

    I just increased it to 45!

  • Kav10 Kav10
    0

    What class level is this for? Regarding questions 1 and 2, can you elaborate a bit more about the "factor trees of a graph"? Do you mean identifying the prime factors of each vertex (assuming the number on the vertex) in the graph provided?

  • Kratos Kratos
    0

    prime factors of each vertex yes!

  • Kratos Kratos
    0

    Let me correct it. It means how many trees can a graph produce with that path

  • Kav10 Kav10
    0

    Thinking more about it, I think it is asking for the number of spanning trees in the graph. And then for the second question, as you said, how many trees in the graph include that path. Thanks for confirming.

Answer

Answers can only be viewed under the following conditions:
  1. The questioner was satisfied with and accepted the answer, or
  2. The answer was evaluated as being 100% correct by the judge.
View the answer

1 Attachment

Kav10 Kav10
1.9K
  • Kav10 Kav10
    0

    @kratos, just to confirm, I have received a $1 tip. Thanks,. If you intended to leave a higher tip, please use a PC or laptop device. This happened with another user and apparently using mobile phone, the system only allows a $1 tip, no matter what number you put as tip.

The answer is accepted.
Join Matchmaticians Affiliate Marketing Program to earn up to a 50% commission on every question that your affiliated users ask or answer.