Number of Hamiltonian cycles in complete graph Kn with constraints
up vote
0
down vote
favorite
I am currently working on a exercice which aims to count the number of hamiltonian cycles in a complete graph. Since it is a completely new topic to me, I struggle to think about how to solve the problem.
I understand how to count the number of Hamiltonian cycles in a complete graph Kn but my main problem is: what if we have constraints on some particular edges that the Hamiltonian must contain?
Here is the exercice with which I'm struggling with
Suppose Kn is a complete graph whose vertices are indexed by
[n] = {1,2,3,...,n} where n >= 4. In this question, a cycle is identied solely by the collection of edges it contains; there is no particular orientation or starting point
associated with a cycle. (Give your answers in terms of n for the following questions.
(a) How many Hamiltonian cycles are there in Kn?
-> My answer : (n-1)!/2. In fact, there is no particular orientation or stationg point, so we can avoid counting the starting point (thus we have n-1)
(b) How many Hamiltonian cycles in Kn contain the edge {1,2}?
-> My answer : since I consider the edge {1,2} as a vertex, the number of HC should be (n-2)!/2
(c) How many Hamiltonian cycles in Kn contain both the edges{1,2} and {2,3}?
-> My Answer : Same reflexion as above, there are (n-3)!/2 hamiltonian cycles
(d) How many Hamiltonian cycles in Kn contain both the edges {1,2} and {3,4}?
-> My question : should I consider {1,2} and {3,4} as proper vertices also?
(e) Suppose that M is a set of k <= n
2 edges in Kn with the property that no two
edges in M share a vertex. How many Hamiltonian cycles in Kn contain all the
edges in M? Give your answer in terms of n and k.
-> Note : Do you have any hint?
(f) How many Hamiltonian cycles in Kn do not contain any edge from {1,2}, {2,3} and {3,4}?
-> Note : Do you have any hint?
Thanks by advance for your help
discrete-mathematics graph-theory hamiltonian-path
asked Nov 24 at 10:21
Cleola
11
add a comment |
up vote
0
down vote
favorite
I am currently working on a exercice which aims to count the number of hamiltonian cycles in a complete graph. Since it is a completely new topic to me, I struggle to think about how to solve the problem.
I understand how to count the number of Hamiltonian cycles in a complete graph Kn but my main problem is: what if we have constraints on some particular edges that the Hamiltonian must contain?
Here is the exercice with which I'm struggling with
Suppose Kn is a complete graph whose vertices are indexed by
[n] = {1,2,3,...,n} where n >= 4. In this question, a cycle is identied solely by the collection of edges it contains; there is no particular orientation or starting point
associated with a cycle. (Give your answers in terms of n for the following questions.
(a) How many Hamiltonian cycles are there in Kn?
-> My answer : (n-1)!/2. In fact, there is no particular orientation or stationg point, so we can avoid counting the starting point (thus we have n-1)
(b) How many Hamiltonian cycles in Kn contain the edge {1,2}?
-> My answer : since I consider the edge {1,2} as a vertex, the number of HC should be (n-2)!/2
(c) How many Hamiltonian cycles in Kn contain both the edges{1,2} and {2,3}?
-> My Answer : Same reflexion as above, there are (n-3)!/2 hamiltonian cycles
(d) How many Hamiltonian cycles in Kn contain both the edges {1,2} and {3,4}?
-> My question : should I consider {1,2} and {3,4} as proper vertices also?
(e) Suppose that M is a set of k <= n
2 edges in Kn with the property that no two
edges in M share a vertex. How many Hamiltonian cycles in Kn contain all the
edges in M? Give your answer in terms of n and k.
-> Note : Do you have any hint?
(f) How many Hamiltonian cycles in Kn do not contain any edge from {1,2}, {2,3} and {3,4}?
-> Note : Do you have any hint?
Thanks by advance for your help
discrete-mathematics graph-theory hamiltonian-path
asked Nov 24 at 10:21
Cleola
11
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I am currently working on a exercice which aims to count the number of hamiltonian cycles in a complete graph. Since it is a completely new topic to me, I struggle to think about how to solve the problem.
I understand how to count the number of Hamiltonian cycles in a complete graph Kn but my main problem is: what if we have constraints on some particular edges that the Hamiltonian must contain?
Here is the exercice with which I'm struggling with
Suppose Kn is a complete graph whose vertices are indexed by
[n] = {1,2,3,...,n} where n >= 4. In this question, a cycle is identied solely by the collection of edges it contains; there is no particular orientation or starting point
associated with a cycle. (Give your answers in terms of n for the following questions.
(a) How many Hamiltonian cycles are there in Kn?
-> My answer : (n-1)!/2. In fact, there is no particular orientation or stationg point, so we can avoid counting the starting point (thus we have n-1)
(b) How many Hamiltonian cycles in Kn contain the edge {1,2}?
-> My answer : since I consider the edge {1,2} as a vertex, the number of HC should be (n-2)!/2
(c) How many Hamiltonian cycles in Kn contain both the edges{1,2} and {2,3}?
-> My Answer : Same reflexion as above, there are (n-3)!/2 hamiltonian cycles
(d) How many Hamiltonian cycles in Kn contain both the edges {1,2} and {3,4}?
-> My question : should I consider {1,2} and {3,4} as proper vertices also?
(e) Suppose that M is a set of k <= n
2 edges in Kn with the property that no two
edges in M share a vertex. How many Hamiltonian cycles in Kn contain all the
edges in M? Give your answer in terms of n and k.
-> Note : Do you have any hint?
(f) How many Hamiltonian cycles in Kn do not contain any edge from {1,2}, {2,3} and {3,4}?
-> Note : Do you have any hint?
Thanks by advance for your help
discrete-mathematics graph-theory hamiltonian-path
asked Nov 24 at 10:21
Cleola
11
I am currently working on a exercice which aims to count the number of hamiltonian cycles in a complete graph. Since it is a completely new topic to me, I struggle to think about how to solve the problem.
I understand how to count the number of Hamiltonian cycles in a complete graph Kn but my main problem is: what if we have constraints on some particular edges that the Hamiltonian must contain?
Here is the exercice with which I'm struggling with
Suppose Kn is a complete graph whose vertices are indexed by
[n] = {1,2,3,...,n} where n >= 4. In this question, a cycle is identied solely by the collection of edges it contains; there is no particular orientation or starting point
associated with a cycle. (Give your answers in terms of n for the following questions.
(a) How many Hamiltonian cycles are there in Kn?
-> My answer : (n-1)!/2. In fact, there is no particular orientation or stationg point, so we can avoid counting the starting point (thus we have n-1)
(b) How many Hamiltonian cycles in Kn contain the edge {1,2}?
-> My answer : since I consider the edge {1,2} as a vertex, the number of HC should be (n-2)!/2
(c) How many Hamiltonian cycles in Kn contain both the edges{1,2} and {2,3}?
-> My Answer : Same reflexion as above, there are (n-3)!/2 hamiltonian cycles
(d) How many Hamiltonian cycles in Kn contain both the edges {1,2} and {3,4}?
-> My question : should I consider {1,2} and {3,4} as proper vertices also?
(e) Suppose that M is a set of k <= n
2 edges in Kn with the property that no two
edges in M share a vertex. How many Hamiltonian cycles in Kn contain all the
edges in M? Give your answer in terms of n and k.
-> Note : Do you have any hint?
(f) How many Hamiltonian cycles in Kn do not contain any edge from {1,2}, {2,3} and {3,4}?
-> Note : Do you have any hint?
Thanks by advance for your help
discrete-mathematics graph-theory hamiltonian-path
discrete-mathematics graph-theory hamiltonian-path
asked Nov 24 at 10:21
Cleola
11
asked Nov 24 at 10:21
Cleola
11
asked Nov 24 at 10:21
Cleola
11
asked Nov 24 at 10:21
Cleola
11
asked Nov 24 at 10:21
Cleola
11
11
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
Q(a)-Q(c) is correct, and Q(d) can be seen as {1,2}{2,3}{3,4} - {2,3} which is 2(n-2)!-(n-3)!
(e) can brake into (12)(34)(56)789
and applying counting,answer=(n)!(n-k-1)!/(2n)
(f)Obviously
Answer=1/2(n-1)!-(n-3)!
answered Nov 30 at 9:19
zacahry
1
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
– José Carlos Santos
Nov 30 at 9:22
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3011395%2fnumber-of-hamiltonian-cycles-in-complete-graph-kn-with-constraints%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
Q(a)-Q(c) is correct, and Q(d) can be seen as {1,2}{2,3}{3,4} - {2,3} which is 2(n-2)!-(n-3)!
(e) can brake into (12)(34)(56)789
and applying counting,answer=(n)!(n-k-1)!/(2n)
(f)Obviously
Answer=1/2(n-1)!-(n-3)!
answered Nov 30 at 9:19
zacahry
1
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
– José Carlos Santos
Nov 30 at 9:22
add a comment |
up vote
0
down vote
Q(a)-Q(c) is correct, and Q(d) can be seen as {1,2}{2,3}{3,4} - {2,3} which is 2(n-2)!-(n-3)!
(e) can brake into (12)(34)(56)789
and applying counting,answer=(n)!(n-k-1)!/(2n)
(f)Obviously
Answer=1/2(n-1)!-(n-3)!
answered Nov 30 at 9:19
zacahry
1
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
– José Carlos Santos
Nov 30 at 9:22
add a comment |
up vote
0
down vote
up vote
0
down vote
Q(a)-Q(c) is correct, and Q(d) can be seen as {1,2}{2,3}{3,4} - {2,3} which is 2(n-2)!-(n-3)!
(e) can brake into (12)(34)(56)789
and applying counting,answer=(n)!(n-k-1)!/(2n)
(f)Obviously
Answer=1/2(n-1)!-(n-3)!
answered Nov 30 at 9:19
zacahry
1
Q(a)-Q(c) is correct, and Q(d) can be seen as {1,2}{2,3}{3,4} - {2,3} which is 2(n-2)!-(n-3)!
(e) can brake into (12)(34)(56)789
and applying counting,answer=(n)!(n-k-1)!/(2n)
(f)Obviously
Answer=1/2(n-1)!-(n-3)!
answered Nov 30 at 9:19
zacahry
1
answered Nov 30 at 9:19
zacahry
1
answered Nov 30 at 9:19
zacahry
1
answered Nov 30 at 9:19
zacahry
1
1
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
– José Carlos Santos
Nov 30 at 9:22
add a comment |
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
– José Carlos Santos
Nov 30 at 9:22
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
– José Carlos Santos
Nov 30 at 9:22
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
– José Carlos Santos
Nov 30 at 9:22
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3011395%2fnumber-of-hamiltonian-cycles-in-complete-graph-kn-with-constraints%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
