MK
Господа
Size: a a a
2021 June 18
MK
Есть несвязный граф заданный в виде матрицы смежности. Как найти число связных подграфов?
MK
Я даже хочу не само число, а его оценку
VS
1. Граф неориентированный?
2. Могут ли 2 различных ребра соединять одни и те же вершины?
2. Могут ли 2 различных ребра соединять одни и те же вершины?
MK
1. неориентированный
2. могут
2. могут
MK
но дубликаты можно поудалять наверное
D
Для каждой компоненты можно посчитать число остовов с помощью матричной теоремы Кирхгофа. Пусть для текущей компоненты это C. Тогда число связных подграфов компоненты точно не превосходит 1/2 * C * 2^{|E_i| - |V_i|}, где |V_i| - число вершин компоненты, |E_i| - число ребер. Для разреженных графов я думаю оценка сойдет.
D
У вас графы плотные или разреженные?
MK
разреженный
SS
написать это куда сложнее чем нарисовать.
В итоге часть стреч всё равно потерял
В итоге часть стреч всё равно потерял
SS
int halfAllEmployee = allEmployees.size() / 2;
// List<Employee> leftSide;
// LinkedList<Employee> rightSide;
//
// leftSide = new ArrayList<>(allEmployees.subList(0, halfAllEmployee));
// rightSide = new LinkedList<>(allEmployees.subList(halfAllEmployee, allEmployees.size()));
//
//
// for (int i = 1; i < rightSide.size()+1; i++) {
// Meets meet = realizeLogicOfMeetings(leftSide, rightSide, i);
// meets.add(meet);
// rightSide.push(rightSide.pollLast());
// }
// for (int i = 0; i < leftSide.size(); i++) {
// Employee employee = leftSide.get(i);
// for (int j = i + 1; j < leftSide.size(); j++) {
// Employee employee1 = leftSide.get(j);
//
// //meets.add(meets.size(), new Audition(employee, employee1));
// }
// }
//
// return meets;
//
// }
//
// private Meets realizeLogicOfMeetings(List<Employee> leftSide, List<Employee> rightSide, int intNumber) {
// List<Audition> current = new ArrayList<>();
// for (int i = 0; i < rightSide.size() && i< leftSide.size(); i++) {
// Employee leftEmployee = leftSide.get(i);
// Employee rightEmployee = rightSide.get(i);
// Audition audition = new Audition(leftEmployee, rightEmployee);
// current.add(audition);
// }
// return new Meets(intNumber, current);
// List<Employee> leftSide;
// LinkedList<Employee> rightSide;
//
// leftSide = new ArrayList<>(allEmployees.subList(0, halfAllEmployee));
// rightSide = new LinkedList<>(allEmployees.subList(halfAllEmployee, allEmployees.size()));
//
//
// for (int i = 1; i < rightSide.size()+1; i++) {
// Meets meet = realizeLogicOfMeetings(leftSide, rightSide, i);
// meets.add(meet);
// rightSide.push(rightSide.pollLast());
// }
// for (int i = 0; i < leftSide.size(); i++) {
// Employee employee = leftSide.get(i);
// for (int j = i + 1; j < leftSide.size(); j++) {
// Employee employee1 = leftSide.get(j);
//
// //meets.add(meets.size(), new Audition(employee, employee1));
// }
// }
//
// return meets;
//
// }
//
// private Meets realizeLogicOfMeetings(List<Employee> leftSide, List<Employee> rightSide, int intNumber) {
// List<Audition> current = new ArrayList<>();
// for (int i = 0; i < rightSide.size() && i< leftSide.size(); i++) {
// Employee leftEmployee = leftSide.get(i);
// Employee rightEmployee = rightSide.get(i);
// Audition audition = new Audition(leftEmployee, rightEmployee);
// current.add(audition);
// }
// return new Meets(intNumber, current);
S
Ну я на плюсах вчера набросал для чётных n
S
А для нечётных нужно чуть повозиться
SS
Да, я тоже намучался
SS
@Override
public @Override
public
public @Override
public
List<Meets> meetingsScheduler() {
List<Employee> allEmployees = getAllEmployees();
List<Meets> meets = new ArrayList<>();
for (int weekNumber = 1; weekNumber < allEmployees.size(); weekNumber++) {
meets.add(new Meets(weekNumber, getPairs(weekNumber, allEmployees)));
}
return meets;
}
private List<Audition> getPairs(int weekNumber, List<Employee> allEmployees) {
List<Audition> result = new ArrayList<>();
for (int i = 0; i < allEmployees.size(); i++) {
Employee firstEmployee = allEmployees.get(i);
int secondIndex = i+weekNumber;
if (secondIndex<allEmployees.size()){
Employee secondEmployee = allEmployees.get(secondIndex);
result.add(new Audition(firstEmployee, secondEmployee));
}
}
return result;
}SS
Вот такая дичь работает, но не правильно
S
А ты типо емплойи в двух разных массивах хранишь?
S
Или как
SS
В
Meet у меня есть дата лист Audition(пара Employee)SS
дата и лист